[LeetCode] 53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/?envType=featured-list&envId=top-interview-questions 

 

 

Kadane's Algorithm (Greedy and DP)

배열의 최대 부분합을 O(n)의 시간 복잡도로 구하는 알고리즘

KEY POINT: 이전의 부분합을 안다면 그 인덱스까지의 부분합은 재계산할 필요가 없다.

 

Greedy: we are keeping a running sum of integers and when it becomes less than 0, we reset it to 0

DP: at each stage, we have 2 choices: Either take the current element and continue with the previous sum OR restart a new range. Both choices are being taken care of in the implementation.

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        curSum, maxSum = 0, nums[0]
        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSum = max(maxSum, curSum)
        return maxSum

 

 

 

Reference

• https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/