Maximum Subarray Sum

Medium · rating 1400 · dp, arrays

The first line contains n. The second line contains n integers. Print the maximum sum of any non-empty contiguous subarray (Kadane's algorithm).

Constraints: 1 ≤ n ≤ 10⁵, |a_i| ≤ 10⁴

Editorial

Approach (Kadane's algorithm)

Scan left to right keeping the best subarray sum ending at the current position. At each element you either extend the previous run or start fresh at the current element — whichever is larger. Track the maximum of those as you go.

Insight

If the running sum ever goes negative it can only hurt what follows, so you drop it and restart. That greedy reset is what makes a single pass sufficient.

best = cur = nums[0]
for x in nums[1:]:
    cur = max(x, cur + x)
    best = max(best, cur)
return best

Complexity

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

Open Maximum Subarray Sum in Code Arena →