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)/2subarrays: 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
- 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].
- 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).
- 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.
- 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
- 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.
- 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. - Time and space? O(n) time, O(1) space.
- How would you return the subarray itself? Track where the current stretch started and save start and end whenever
bestimproves. - 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 fromnums[0].- O(n) time, O(1) space, and all-negative arrays work.
Next episode: Prefix sums: count the subarrays whose sum equals K.