Blind 75Medium

Maximum Subarray — Kadane’s Running Sum

Carry a running best prefix; reset when it becomes negative so the subarray that follows starts fresh.

Dynamic ProgrammingArray

View problem on LeetCode

Problem Statement

Return the largest sum over all contiguous subarrays.

Why This Problem Matters

Classic example of dynamic programming on a line.
Teaches the idea of dropping harmful prefixes to preserve future sums.
Forms the basis for stock profit, circular subarray, and 2D variants.

Thought Process

Track running sum

Maintain currentSum as the best subarray ending at index i. If currentSum becomes negative, restart at the next element.

Update global best

At each step, maxSum keeps the best seen so far, regardless of where it ends.

Handle all-negative arrays

Initialise maxSum to the first element so the algorithm returns the least negative value.

Step-by-Step Reasoning

Set currentSum = maxSum = nums[0].
For each num in nums[1:], update currentSum = Math.max(num, currentSum + num).
Refresh maxSum = Math.max(maxSum, currentSum).
Return maxSum after the loop.

Dry Run

nums = [-2,1,-3,4,-1,2,1,-5,4]

currentSum resets at 4; final answer 6 from subarray [4,-1,2,1].

nums = [-3,-2,-1]

maxSum initialised to -3, updated to -2 then -1.

Complexity Analysis

Time

O(n)

Space

O(1)

Why

Single pass maintaining constant extra state.

Annotated Solution

JAVA

public class MaximumSubarray {
  public int maxSubArray(int[] nums) {
    int current = nums[0];
    int best = nums[0];

    for (int i = 1; i < nums.length; i += 1) {
      int num = nums[i];
      current = Math.max(num, current + num);
      best = Math.max(best, current);
    }

    return best;
  }
}

Kadane’s algorithm maintains the best subarray ending at each index. Dropping negative prefixes keeps the total optimal.

Common Pitfalls

Setting currentSum to zero when negative incorrectly returns 0 for all-negative arrays.
Forgetting to update maxSum before altering currentSum loses track of the best value.
Mixing integer overflow checks when numbers can be large; mention constraints if relevant.

Follow-Up Questions

How would you track the actual subarray indices?
What changes for a circular array where wrapping is allowed?

Key Takeaways

Resetting when the running sum drops below zero is the core Kadane insight.

Always initialise using the first element to handle all-negative inputs.

This template reappears in many DP questions—remember it well.