Kadane's Algorithm Pattern

Why this pattern matters for LeetCode

The brute force checks every possible subarray by computing its sum from scratch each time. That is O(n²). Kadane's is O(n) because it makes one local decision at each element: extend or restart. If the running sum is positive, extending can only help. If it's negative, you're better off starting fresh from the current element. You never need to look backward — just the running sum and the current element.

What the Kadane's Algorithm pattern is

Kadane's Algorithm maintains two values as it scans: currentSum (the best sum of any subarray ending at the current position) and maxSum (the best seen anywhere so far). At each element, currentSum = max(nums[i], currentSum + nums[i]). This is the 'extend or restart' decision: take just this element alone, or add it to the running total. Update maxSum whenever currentSum improves it.

Reach for Kadane's Algorithm when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Kadane's Algorithm

• ✓Maximum subarray sum (the classic Kadane's problem)
• ✓Minimum subarray sum (negate all values and find the max)
• ✓Maximum product subarray (modified Kadane's tracking both max and min)
• ✓Any problem where the optimal contiguous subarray is determined greedily element by element

When NOT to use Kadane's Algorithm

• ✕The subarray doesn't need to be contiguous — use a different approach
• ✕You need to return the actual subarray, not just the sum — you can extend Kadane's to track start/end, but it's more complex
• ✕The constraint involves a fixed window size — use Sliding Window instead
• ✕You need the sum of k largest elements — use a heap or sort

Better alternative: In those cases, Sliding Window (for fixed-size windows) or a prefix sum approach may be more appropriate.

JavaScript code template

Maximum Subarray — O(n) time, O(1) space

function maxSubArray(nums) {
  // Initialize to nums[0], NOT 0 — handles all-negative arrays correctly
  let maxSum = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    // Extend the current subarray, or restart from nums[i] alone?
    currentSum = Math.max(nums[i], currentSum + nums[i]);

    // Did we just find a new best?
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}

Both values start at nums[0] to handle all-negative arrays correctly. Starting at index 1, the extend-or-restart decision runs at each element: if currentSum + nums[i] > nums[i], the existing streak is helping — extend it. Otherwise, it's a drag — restart from nums[i] alone. maxSum captures the best currentSum seen across the entire scan.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Initialize maxSum = nums[0] and currentSum = nums[0] — NOT zero.
2. 2Start the loop at index 1 (not 0, since nums[0] is already accounted for).
3. 3At each element: currentSum = Math.max(nums[i], currentSum + nums[i]).
4. 4This is the extend-or-restart decision — whichever is larger wins.
5. 5Update maxSum = Math.max(maxSum, currentSum) to track the global best.
6. 6Return maxSum after the loop.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Maximum Subarray

  The textbook Kadane's problem — extend or restart at each element, track the maximum.

  Premium→
• Maximum Product Subarray

  Modified Kadane's — track both max and min because a negative times a negative can flip to the largest positive.

  Premium→
• Best Time to Buy and Sell Stock

  Closely related — tracks the best opportunity seen so far (minimum price) as you scan forward.

  Premium→

Coming soon

• Maximum Sum Circular Subarray

  Max of: standard Kadane's on the array, or total sum minus minimum subarray sum.

  Coming soon

Common mistakes beginners make

• ✕Initializing maxSum or currentSum to 0 — this fails when all elements are negative. The answer should be the least negative number, not 0.
• ✕Starting the loop at index 0 after initializing both values from nums[0] — you'll double-count the first element.
• ✕Forgetting to update maxSum inside the loop — if you only update at the end, you'll miss the true maximum.
• ✕Confusing currentSum (best subarray ending here) with maxSum (best subarray seen anywhere) — you need both and they serve different roles.

Kadane's vs Sliding Window vs Dynamic Programming

Choose the right tool for the job.

Time and space complexity

One pass through the array — each element is visited exactly once. The two variables (currentSum, maxSum) take O(1) space. No recursion, no extra arrays. This is as lean as it gets for a subarray problem.

Frequently asked questions

Why do we initialize to nums[0] instead of 0?

If you initialize maxSum to 0 and all numbers are negative, you'll return 0 — but 0 isn't a valid subarray answer (the problem requires at least one element). Initializing to nums[0] ensures you always return the least negative element in an all-negative array.

What does 'extend or restart' actually mean?

At each element nums[i], you choose between: starting a brand new subarray at nums[i] (restart), or adding nums[i] to whatever subarray ended at i-1 (extend). You pick whichever gives a larger currentSum. If currentSum was negative, extending always makes things worse — so you restart.

Is Kadane's Algorithm a form of dynamic programming?

Yes, technically. The recurrence is: dp[i] = max(nums[i], dp[i-1] + nums[i]), where dp[i] is the maximum subarray sum ending at index i. Kadane's is the space-optimized version — instead of keeping the entire dp array, you only keep the previous value (currentSum). The answer is max of all dp[i] values (maxSum).

What happens with all-negative input like [-3, -1, -2]?

Kadane's handles it correctly when initialized to nums[0]. Both maxSum and currentSum start at -3. At index 1: currentSum = max(-1, -3 + (-1)) = max(-1, -4) = -1. maxSum = max(-3, -1) = -1. At index 2: currentSum = max(-2, -1 + (-2)) = max(-2, -3) = -2. maxSum stays -1. Correct answer: -1.

How is Kadane's different from a sliding window?

Kadane's doesn't maintain an explicit window — it 'resets' the window whenever starting fresh is better. A sliding window maintains a well-defined range [left, right] and adjusts it based on a constraint. Kadane's constraint ('is the running sum positive?') collapses the window tracking into a single variable.