[Leetcode] 53. Maximum Subarray

문제 바로가기

Time Complexity: O(n)
Space Complexity: O(1)

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSubSum = subSumSoFar = nums[0]
        
        for i in range(1, len(nums)):
            # Initialize if the previous subsum is negative
            if subSumSoFar < 0:
                subSumSoFar = 0
            subSumSoFar += nums[i]
            
            if maxSubSum < subSumSoFar:
            	maxSubSum = subSumSoFar
        
        return maxSubSum

Kadane's Algorithm

각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값임을 활용하자.

배열의 각 인덱스에서 가질 수 있는 최대 부분 값은 자신의 값과 이전의 최대 부분합에 자신의 값의 합 중 더 큰 것을 선택하면 된다. 즉, 이전 인덱스의 최대 부분합이 음수라면 자신의 값을 선택하면 되는 것이다. 이 과정을 거치면 최종적으로 각 인덱스에서 얻을 수 있는 최대 부분합의 배열을 얻을 수 있다.

이 중 최대 값이 전체 부분 합중 최대 값이 된다.

참고
Kadane's Algorithm - 블로그