MaximumSubarray

Published at 2021-10-22

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

    # [3,-1,2,-4,-1] 이 있다고 했을 때
    # [:1]만 있다고 해보자 . 그럼 [3] 인데 그 중에서 maxSubArray의 합계는 당연 3임
    # 다음 [:2]만 있다? (여기서 [1]은 무조건 포함되는 값임) 그럼 [3, -1]인데 -1에 3을 더할거냐 말거냐. 더하는게 낫지. => 더해서 2로 갱신한다. [3,2,2,-4...]이 됨
    # 그 다음 [:3] => 인덱스2의 값은 무조건 포함임. 이 전에서 [:2]만 있을때 [0:2]를 전부 포함하는게 더 이득이었지? 그럼 갱신된 2가 저장된 [i-1]의 값을 현재위치에 갱신함
    # 그럼 [3,2,4,-4,-1]이겠지
    # 다음 이제 i=3이라서 [:4]를 보자. 이 바로 전에는 이미 최적의 답이 저장된 상태임. 그 값이 4니까 얘랑 나(-4)를 더하는게 나한텐 이득임. 그러니 더해서 0으로 갱신
    # [3,2,4,0,-1] 인데 마지막 -1은 앞의 0을 더해봤자 의미가 없다. 그러니 걍 패스하자
    # 최종 nums를 살펴봐서 max값을 리턴하면 끝