LeetCode > 53. Maximum Subarray

문제 링크 : https://leetcode.com/problems/maximum-subarray/

연속되는 subarray 중에서 가장 큰 합을 가지는 subarray를 찾아서 합을 리턴하라.

dp를 이용하여 풀 수 있다.

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i] = max(nums[i-1]+nums[i],nums[i])
            
        return max(nums)
            

....

1. nums[i] = max(nums[i-1] + nums[i], nums[i])에서 이 전의 값과 지금의 값의 합, 지금의 값 둘 중에 큰 값으로 대체한다. 인덱스가 1부터 시작이므로 [-2,1,-3,4,-1,2,1,-5,4] 여기서 -2 + 1 = -1, 1 둘 중에 1이 더 크니까 [-2,1,-3,4,-1,2,1,-5,4] 가 된다.

2. 1 + (-3) = -2, -3 둘 중에 -2가 더 크므로 [-2,1,-2,4,-1,2,1,-5,4] 이다.

3. -2 + 4 = 2, 4 둘 중 원래 있던 4가 더 크므로 지금까지 앞에서 더해온 것들을 가지고 계속 더해가는건 더 손해므로 과감히 버리고 새출발을 한다.
   이런 식으로 진행해 나가면 가장 큰 부분 합을 구할 수 있다.

   ---

   다시 풀었는데도 생각보다 dp문제는 쉽지 않았다....