Skip to content
Codeloom
DSA

Maximum Subarray — Kadane's Algorithm Explained

A clear walkthrough of Maximum Subarray. We build Kadane's algorithm from first principles and contrast it with the divide and conquer approach.

·5 min read · By Codeloom
Intermediate 10 min read

What you'll learn

  • ✓Brute-force approach and its complexity
  • ✓Optimal approach with intuition
  • ✓Edge cases that trip people up
  • ✓How to talk through it in an interview
  • ✓Related problems to follow up with

Prerequisites

Maximum Subarray is the canonical introduction to Kadane’s algorithm. Once you understand why it works, you understand the core idea behind one-dimensional dynamic programming.

The Problem

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The subarray must have at least one element.

Example:

Input:  nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has sum 6.

“Contiguous” is the operative word. We are not picking arbitrary elements; we are picking a window.

Intuition

The brute force tries every subarray, accumulating sums — O(n^2). For n = 10^5 that is too slow.

Kadane asks at each index: “what is the maximum sum of a subarray ending exactly here?” Call it current. The recurrence is simple: either extend the previous best ending subarray, or start fresh at this element — whichever is larger. The global answer is the max of current across all indices.

The justification is subtle but small: if current + x < x, then current was negative, and dragging it forward can only hurt. Throw it away. This monotonicity is what makes the algorithm correct.

Explanation with Example

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

  • Start: current = -2, best = -2.
  • x = 1. current = max(1, -2 + 1) = 1. best = 1.
  • x = -3. current = max(-3, 1 + -3) = -2. best = 1.
  • x = 4. current = max(4, -2 + 4) = 4. best = 4.
  • x = -1. current = max(-1, 4 + -1) = 3. best = 4.
  • x = 2. current = max(2, 3 + 2) = 5. best = 5.
  • x = 1. current = max(1, 5 + 1) = 6. best = 6.
  • x = -5. current = max(-5, 6 + -5) = 1. best = 6.
  • x = 4. current = max(4, 1 + 4) = 5. best = 6.

Return 6.

idx       0   1   2   3   4   5   6   7   8
nums     -2   1  -3   4  -1   2   1  -5   4
current  -2   1  -2   4   3   5   6   1   5
best     -2   1   1   4   4   5   6   6   6
                       [---- best window ----]
                          4 + -1 + 2 + 1 = 6
current restarts when sum goes negative; best tracks peak

Code

def max_subarray(nums):
    current = nums[0]
    best = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best
class Solution {
    public int maxSubArray(int[] nums) {
        int current = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }
        return best;
    }
}
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int current = nums[0], best = nums[0];
        for (size_t i = 1; i < nums.size(); ++i) {
            current = max(nums[i], current + nums[i]);
            best = max(best, current);
        }
        return best;
    }
};

Edge Cases

  • All negative numbers like [-3, -1, -2]. The answer is -1, the single largest element. The algorithm handles this because we initialize with nums[0] rather than 0.
  • Single element. Return that element.
  • All zeros. Return 0.
  • Mixed signs with a strong positive run at the end. Make sure your best actually updates inside the loop.
  • Asked for the subarray itself, not just the sum. Track start and end indices alongside.

Complexity Analysis

  • Time: O(n). One pass.
  • Space: O(1). Two scalars.

A divide and conquer solution exists at O(n log n) but it is strictly slower.

How to Explain It in an Interview

  • Restate the problem and confirm “contiguous” and “at least one element.”
  • Mention brute force at O(n^2) so they know you see the baseline.
  • State the Kadane insight: “I will compute, for each index, the best subarray ending there. Take this element alone or extend the previous best.”
  • Justify dropping a negative running sum: it can only hurt.
  • Code it, walk through a small example.
  • Mention the all-negative edge case explicitly.

To see how “extend or restart” generalizes, the sliding window technique post is the natural next read.

Wrap up

Kadane’s is small enough to fit on a sticky note and deep enough to be a poster child for DP. The mental model — “best answer ending right here given the best ending one step back” — scales up to longest increasing subsequence, edit distance, and most of the DP canon.

Related articles