Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 53 Maximum Subarray - Implementation

The approach

Kadane's algorithm. Single pass.

def maxSubArray(nums): currentSum = maxSum = nums[0]

for i in range(1, len(nums)):
    currentSum = max(nums[i], currentSum + nums[i])
    maxSum = max(maxSum, currentSum)

return maxSum

O(n)O(n) time, O(1)O(1) space.