Kadane's Algorithm - The Maximum Subarray Problem

1. The problem

Given an integer array, find the maximum sum of any non-empty contiguous subarray. Contiguous means selected elements sit next to one another in the original array.

Example:

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

The best subarray is [4, -1, 2, 1] , with sum 6 .

A straightforward running-sum brute-force approach can take O(n²) time. Kadane's Algorithm solves the problem in O(n) time and O(1) auxiliary space.

2. The intuition

At every element x, choose between:

• Extend the previous subarray: currentSum + x
• Restart at the current element: x

currentSum = max(x, currentSum + x)
maxSum = max(maxSum, currentSum)

currentSum is the best sum of a non-empty subarray ending exactly at the current index. maxSum is the best sum found anywhere so far.

The important idea is that a negative running sum cannot improve a future subarray. If starting at the current element gives a larger sum than extending, discard the previous running subarray and restart.

3. Working: step-by-step dry run

Let's trace the example from left to right:

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

Initialize both currentSum and maxSum with the first element, -2. We do this because the subarray must contain at least one element.

For each next element:

1. Extend = previous currentSum + current element
2. Restart = current element by itself
3. currentSum = the larger of Extend and Restart
4. maxSum = the larger of the previous maxSum and the new currentSum

i) What should you notice?

• At index 1, extending gives -1, but restarting gives 1. So we start a new subarray at 1.
• At index 3, extending gives 2, but restarting gives 4. The negative running sum before it would only reduce the sum, so we restart at 4.
• From index 3 through index 6, the running sum becomes 4, 3, 5, then 6.
• At index 7, the current sum drops from 6 to 1, but maxSum stays 6. The best answer found so far should not be lost just because the current subarray becomes worse.
• The final currentSum is 5, but the final maxSum is still 6.

Final answer: 6, from the subarray [4, -1, 2, 1].

4. C++ implementation

int maxSubArray(vector<int>& nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];
 
    for (int i = 1; i < nums.size(); i++) {
        currentSum = max(nums[i], currentSum + nums[i]);
        maxSum = max(maxSum, currentSum);
    }
 
    return maxSum;
}

This implementation assumes the array is non-empty.

5. Complexity

• Time: O(n) — each element is processed once.
• Auxiliary space: O(1) — only a constant number of variables are used.

6. Edge cases and mistakes

• All-negative array: the answer is the largest (least negative) element, not zero.
• One element: that element is the answer.
• Zeros: zero may be the maximum sum, and multiple subarrays can tie.
• Initialization: initialize both variables with nums[0] because the subarray must be non-empty.
• Sum versus indices: the code above returns the maximum sum, not the boundaries of the subarray.
• Empty input: define expected behavior separately if empty arrays are allowed.

7. Quick revision

At each position, extend the best subarray ending just before it or start a new subarray, then update the best sum seen overall.

currentSum = max(nums[i], currentSum + nums[i])
maxSum = max(maxSum, currentSum)

Remember the difference:

• currentSum: best sum of a subarray ending at this index.
• maxSum: best sum found anywhere so far.

8. Test yourself

Try this array:

[-4, 2, -1, 3, -7]

Question: What is the maximum sum, and which contiguous subarray produces it?

9. Practice problems and references

i) Direct practice

• LeetCode 53 — Maximum Subarray — the classic maximum-subarray problem.
• GeeksforGeeks — Kadane's Algorithm — practice the standard maximum-subarray-sum version.
• HackerRank — The Maximum Subarray — a related problem that asks about contiguous and non-contiguous subsequences.

ii) Related applications and extensions

• Codeforces 327A — Flipping Game — a related application where the gain from flipping a segment can be modelled as a maximum-subarray problem.
• GeeksforGeeks — Print the Maximum Subarray Sum — extend the idea to recover the actual subarray, not just its sum.
• CSES — Subarray Sum Queries — a more advanced extension involving updates and maximum-subarray queries; this typically requires a segment tree rather than plain Kadane's Algorithm.

Notes

• Kadane's Algorithm is a one-pass dynamic programming approach.
• Its key state is the best subarray sum ending at the current position.
• Keep this distinction clear: the best subarray ending here can decrease, while the best answer found overall never decreases.