[Leetcode/파이썬] 53. Maximum Subarray

Maximum Subarray

---

Given an integer array nums, find the subarray with the largest sum, and return its sum.

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

 

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

 

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1 :
            return nums[0]

        res = nums[0]   # nums.length가 최소 1이기 때문에 가장 처음 수로 설정
        tmp = 0

        for i in range(len(nums)) :
            tmp += nums[i]  # 0에다가 nums[i]를 더함
            res = max(res, tmp)
            if tmp < 0 :
                tmp = 0

        return res

엄청 헤맸는데 잘 풀렸다. 생각해보니 가장 첫번째 if문은 없어도 쉽게 풀리는 문제인데 넣으면 조금 더 빠르게 동작하니, 기호에 맞춰 넣으면 된다. 사실 풀고 나서 알았다.

첫 번째 수로 0으로 시작했었다. 근데 길이가 1인 배열에서는 0으로 하면 안되잖아? 그래서 고민하다가 첫번째 수를 넣자 해서 넣었더니 정답이 되었다. 임시의 수로 tmp을 작성한 후 for문을 작성했다.

tmp 에는 현재의 수를 하나씩 더한다. 그리고 res 는 현재의 res와 tmp 값을 비교 후 더 큰 값으로 갱신, 만약 tmp가 음수라면 0으로 초기화해 처음부터 다시 시작하도록 하였다.

어떻게 보면 바로 전 문제인 Gas Station과 굉장히 유사한 문제라고 생각이 들었다. 똑같이 그리디로 풀었네... 

문제의 조언에 따르면 분할 정복 방법으로도 풀어보라고 하니 나중에 공부해야지.

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        tmp = 0

        for num in nums :
            if tmp < 0 :
                tmp = 0

            tmp += num
            res = max(res, tmp)

        return res
'''
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1 :
            return nums[0]

        mid = len(nums) // 2
        left_max = self.maxSubArray(nums[:mid])
        right_max = self.maxSubArray(nums[mid:])

        left_sum = float('-inf')
        sm = 0
        for i in range(mid-1, -1, -1) :
            sm += nums[i]
            left_sum = max(left_sum, sm)

        right_sum = float('-inf')
        sm = 0
        for i in range(mid, len(nums)) :
            sm += nums[i]
            right_sum = max(right_sum, sm)

        cross_max = left_sum + right_sum

        return max(left_max, right_max, cross_max)
'''

다른 사람 코드를 참고하고 풀었다. 분할정복도 공부해봐야겠다.