SyntaxPilot
Courses/DSA and Coding Problems/Lesson 4
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 4 of 90

Kadane's algorithm: maximum subarray

queued

These are the notes for DSA episode 4. The maximum subarray problem (LeetCode 53) asks for the consecutive stretch with the biggest sum. Trying every stretch is O(n²) or O(n³); Kadane's algorithm solves it in one pass with one decision per element: extend the current stretch, or start fresh. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.

The problem, in real life

Raju runs a chai stall and writes down each day's profit (in ₹100s). Rainy days are losses, so some numbers are negative:

-2, 1, -3, 4, -1, 2, 1, -5, 4

For his poster, he wants the best run ever: one unbroken stretch of consecutive days with the biggest total.

Problem statement

Given an integer array nums (n ≥ 1), find the subarray with the largest sum and return that sum. Constraints: 1 ≤ n ≤ 10⁵, values between -10⁴ and 10⁴.

A subarray is a consecutive, non-empty part of the array. You can start and stop anywhere, but you can't skip elements (skipping gives a subsequence, a different problem).

nums answer best subarray
[-2, 1, -3, 4, -1, 2, 1, -5, 4] 6 [4, -1, 2, 1]
[-3, -1, -2] -1 [-1]
[5] 5 [5]
[5, -2, 3] 6 [5, -2, 3]: the loss is worth carrying

Brute force: every start, every end

public class Main {
    static int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                best = Math.max(best, sum);
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}

Output:

6

On ten lakh (1,000,000) days:

int n = 1000000, nums[] = new int[n];
for (int i = 0; i < n; i++) nums[i] = (int) (i * 7919L % 201) - 100;
System.out.println(maxSubArray(nums));
Time Limit Exceeded (8 s)

Why it is slow

  • An array of n elements has n(n+1)/2 subarrays: O(n²) even with a running sum, and O(n³) if each subarray is summed from scratch.
  • Flip the question: fix the end day i. The best stretch ending at i is nums[i] plus the best stretch ending at i - 1, but only if that helps. If the stretch ending at i - 1 has a negative sum, it is a debt: day i does better on its own.

The key insight: a negative running sum is a debt

Raju's khata (ledger): keep a running total for the current stretch. If the total is in loss, carrying it forward only drags every future day down, so close the old khata and open a fresh one today.

cur  = max(nums[i], cur + nums[i])   // best sum of a subarray ENDING at i
best = max(best, cur)                // best sum seen anywhere

Dry run: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i nums[i] extend (cur + x) restart (x) cur best
0 -2 — -2 -2 -2
1 1 -1 1 1 1
2 -3 -2 -3 -2 1
3 4 2 4 4 4
4 -1 3 -1 3 4
5 2 5 2 5 5
6 1 6 1 6 6
7 -5 1 -5 1 6
8 4 5 4 5 6

The best stretch is days 3 to 6: 4 - 1 + 2 + 1 = 6.

Kadane's algorithm

public class Main {
    static int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(maxSubArray(new int[]{-3, -1, -2}));
        System.out.println(maxSubArray(new int[]{5}));
        System.out.println(maxSubArray(new int[]{5, -2, 3}));
    }
}

Output:

6
-1
5
6

On one crore (10,000,000) days it takes a few milliseconds:

591   23 ms

The same solution in C++ and Python

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    cout << maxSubArray({-2, 1, -3, 4, -1, 2, 1, -5, 4}) << "\n";   // 6
    cout << maxSubArray({-3, -1, -2}) << "\n";                      // -1
}
def max_sub_array(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

print(max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]))   # 6
print(max_sub_array([-3, -1, -2]))                      # -1

Complexity

Approach Time Extra space n = 10⁶
Every subarray, summed from scratch O(n³) O(1) hopeless
Every subarray with a running sum O(n²) O(1) Time Limit Exceeded
Kadane O(n) O(1) milliseconds

cur is "the best answer ending at i", built from "the best answer ending at i - 1": your first taste of dynamic programming.

Printing the start and end

public class Main {
    public static void main(String[] args) {
        int[] a = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int cur = 0, best = Integer.MIN_VALUE, start = 0, bestL = 0, bestR = 0;
        for (int i = 0; i < a.length; i++) {
            if (cur <= 0) { cur = a[i]; start = i; }
            else cur += a[i];
            if (cur > best) {
                best = cur;
                bestL = start;
                bestR = i;
            }
        }
        System.out.println("Days " + bestL + " to " + bestR + ", sum " + best);
    }
}

Output:

Days 3 to 6, sum 6

When cur ≤ 0, the old stretch is no help, so the new stretch starts at i.

Kadane inside the stock problem

Episode 3's prices 7, 1, 5, 3, 6, 4 have daily changes -6, +4, -2, +3, -2. Buying on day 1 and selling on day 4 earns +4 - 2 + 3 = 5: the profit of any trade is the sum of a stretch of daily changes. So the best trade is the maximum subarray of the daily changes (or 0 if it is negative).

Common mistakes

Mistake What you see Why Fix
int cur = 0, best = 0; and reset to 0 when negative 0 for [-3, -1, -2] (answer is -1) 0 means an empty subarray, which is not allowed start cur and best at nums[0]
nums[0] on an empty array ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0 there is no first element check nums.length (the problem promises n ≥ 1)
best = Math.max(best, nums[i]); 4 for Raju's days (answer is 6) finds the best single day, not the best stretch best = Math.max(best, cur)
picking 4, 2, 1, 4 11: not a valid answer subarrays can't skip elements consecutive elements only

Practice

  1. Minimum subarray sum of [3, -4, 2, -3, -1, 7, -5].
Solution

Flip Kadane: cur = min(x, cur + x), best = min(best, cur). Answer: -6 from [-4, 2, -3, -1].

  1. Maximum product subarray of [2, 3, -2, 4] and [-2, 3, -4].
Solution

A negative times a negative is positive, so track both the largest and the smallest product ending at i:

int hi = a[0], lo = a[0], best = a[0];
for (int i = 1; i < a.length; i++) {
    int x = a[i];
    int h = Math.max(x, Math.max(hi * x, lo * x));
    int l = Math.min(x, Math.min(hi * x, lo * x));
    hi = h; lo = l;
    best = Math.max(best, hi);
}

Answers: 6 ([2, 3]) and 24 (the whole array).

  1. Print the best stretch for [-3, -1, -2].
Solution

The start/end program above prints Days 1 to 1, sum -1: with all negatives the best "stretch" is the single largest element.

  1. Maximum subarray sum in a circular array, where the end wraps to the start ([5, -3, 5] → 10).
Solution

Either the best subarray doesn't wrap (normal Kadane), or it wraps, which means it is the total minus the minimum subarray. Answer = max(kadaneMax, total - kadaneMin), except when every number is negative, then it is just kadaneMax. For [5, -3, 5]: max(7, 7 - (-3)) = 10.

Quick quiz

What does maxSubArray(new int[]{2, -3, 5, -1, 6, -10, 4}) return?

  • 10
  • 11
  • 6
  • 4
Answer

10. cur goes 2, -1, 5 (restarting beats extending: 5 > 4), 4, 10, 0, 4. The best stretch is 5, -1, 6.

Interview questions

  1. Explain Kadane in one sentence. For each element, the best subarray ending there either extends the best one ending at the previous element or starts fresh; the answer is the best of these.
  2. Why does starting at nums[0] handle all-negative arrays? The answer is never empty, so it must be at least the largest single element; starting at 0 would wrongly allow an empty subarray.
  3. Time and space? O(n) time, O(1) space.
  4. How would you return the subarray itself? Track where the current stretch started and save start and end whenever best improves.
  5. Is Kadane dynamic programming? Yes: cur[i] = max(nums[i], cur[i-1] + nums[i]) is a DP recurrence, kept in one variable because only the previous value is needed.

Glossary

Term Meaning
Subarray A consecutive, non-empty part of an array
Subsequence Elements in order but possibly with gaps (not a subarray)
Running sum The total of the current stretch, updated as you move
cur The best sum of a subarray that ends exactly at the current index
best The best subarray sum found anywhere so far
Kadane's algorithm The one-pass "extend or restart" method for the maximum subarray
Recurrence A formula that defines the answer at step i from earlier steps
Dynamic programming Solving a problem by building answers from smaller, already-solved ones
Circular array An array whose end wraps around to its start

Summary

  • A subarray is consecutive and non-empty; there are O(n²) of them.
  • A negative running sum is a debt: restart instead of extending.
  • cur = max(x, cur + x), best = max(best, cur), starting from nums[0].
  • O(n) time, O(1) space, and all-negative arrays work.

Next episode: Prefix sums: count the subarrays whose sum equals K.