[leetcode] 최대 서브 배열

Maximum Subarray
링크텍스트
nums 배열에서 배열의 합이 최대가 되는 서브 배열의 합을 구하는 문제이다. 이때, 서브 배열은 배열 안에서 연속된 요소로 이루어져야 한다.
nums = [-2,1,-3,4,-1,2,1,-5,4] 일 경우,
배열의 합이 최대가 되는 서브 배열은 [4, -1, 2, 1] 이고, 이 배열의 합은 6이기 때문이 답은 6이 된다.

sums라는 배열을 만들어서 앞에서부터 이 안에 배열의 합을 저장해 나간다.
이때, 여태 앞에서 더해온 sums가 음수값이 될 경우, 이 값들을 버리고 새로 sums를 더하기 시작한다. (sums[i] = 0 + nums[i])
이렇게 저장해 나간다면 최종적으로 sums 배열에 저장된 값들 중 최대값이 답이 될 것이다.

nums: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
sums: [-2, 1, -2, 4, 3, 5, 6, 1, 5]

class Solution(object):
    def maxSubArray(self, nums):
        sums = [0] * len(nums)
        sums[0] = nums[0]
        for i in range(1, len(sums)):
            if sums[i-1] < 0:
                sums[i] = 0 + nums[i]	# 앞의 값들 버리고 다시 시작
            else:
                sums[i] = sums[i-1] + nums[i]	
        return max(sums)