Loading…

mediumArraysLC #53Asked very often

Maximum Subarray (Kadane's)

Q: How do you solve Maximum Subarray (Kadane's) using the Brute Force — Sum Every Subarray approach?

When to use it: Say it first to anchor the O(n²) baseline, then pivot to 'we can avoid recomputing sums by carrying a running total' — that transition leads straight to Kadane's. Enumerate every contiguous subarray and keep the largest sum. Fix a start index `i`, then sweep an end index `j` from `i` to the end, accumulating `nums[j]` into a running total and comparing it against the global best. **Why carry a running sum instead of re-summing.** A naive triple loop (recomputing each subarray's sum from scratch) is O(n³). By keeping a `sum` that we extend as `j` advances, scoring each subarray costs O(1) and the whole thing drops to O(n²). It's worth saying this out loud — it shows you optimise inside a loop before throwing the whole approach away. **Why this is the honest first answer.** It directly encodes the definition: 'try all contiguous subarrays, take the max'. It's obviously correct and a good warm-up to reason about, which is exactly what an interviewer wants to hear before the clever pass. For `n = 10⁵` (the constraint) O(n²) is ~10¹⁰ operations and will time out — so we present it, state the cost, and improve. **Why it sets up Kadane's.** Notice the inner loop already maintains 'the sum of the subarray ending at `j` that started at `i`'. Kadane's insight is that we don't need to try every start `i` independently — we can decide, in one pass, whether to keep extending the current run or to abandon it. That observation collapses the outer loop entirely. Time complexity: O(n²). Space complexity: O(1).

Q: How do you solve Maximum Subarray (Kadane's) using the Kadane's Algorithm — One-Pass Running Sum (Optimal) approach?

When to use it: The answer they want. Frame it as 'best subarray ending at each index' and explain the negative-prefix reset — don't just recite the two lines. Walk the array once, maintaining `cur` = the largest sum of a subarray that *ends at the current index*, and `best` = the largest `cur` seen so far. At each element, `cur = max(num, cur + num)` and `best = max(best, cur)`. **Why 'best ending here' is the right state.** Any maximum subarray has to end *somewhere*. If, for every index, we know the best subarray that ends exactly there, then the overall answer is just the maximum of those per-index bests. So we reduce a 2D search (start, end) to a 1D scan: only the end index moves, and `cur` summarises the best choice of start for that end. **Why we reset when the prefix goes negative.** The choice `cur = max(num, cur + num)` says: either glue `num` onto the run ending at the previous index, or throw that run away and begin fresh at `num`. Starting fresh wins exactly when `cur + num < num`, i.e. when `cur < 0`. The reasoning is airtight — if the sum accumulated so far is negative, it can only *reduce* the total of anything we extend it into, so the optimal subarray ending here would never include that negative prefix. Drop it. **Why `cur` and `best` are separate.** `cur` is allowed to fall (and reset) as we move right; it tracks a local, end-anchored quantity. `best` is the high-water mark that never decreases. Conflating them — for example returning `cur` at the end — would report the sum of the *last* run instead of the largest run anywhere. **Why initialise to `nums[0]` and not 0.** The subarray must be non-empty, and an all-negative array's answer is its least-negative element. Seeding `cur = best = nums[0]` and scanning from index 1 guarantees we never invent an empty (sum-0) subarray. Time complexity: O(n). Space complexity: O(1).

LCPractice

Dynamic Programming · 1 of 44 · 8 min

Given an integer array nums, find the **contiguous** subarray (containing at least one number) which has the largest sum, and return its sum.

A subarray is a contiguous part of an array.

In plain English

Among all contiguous slices of the array, find the one whose elements add up to the most. The slice must be non-empty and unbroken — you can't skip elements in the middle. With negatives in play, the trick is knowing when to abandon a losing run.

Examples

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Note: The subarray [4, -1, 2, 1] sums to 6 — the best contiguous run.

Example 2

Input: nums = [1]
Output: 1
Note: A single element is its own best subarray.

Example 3

Input: nums = [-3, -1, -2]
Output: -1
Note: All negative — the best you can do is the single largest element, -1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
The subarray must contain at least one element
Elements may be negative, zero, or positive

Clarifying questions4First question: Does the subarray have to be contiguous?Explore questions

Q1.Does the subarray have to be contiguous?
Yes — that's the whole problem. If gaps were allowed you'd just sum all the positives; contiguity is what makes the running-sum reset necessary.
Q2.Can the array be all negative?
Yes. [-3, -1, -2] must return -1, the largest single element. This is why you can't initialise the answer to 0.
Q3.Is an empty subarray allowed?
No — at least one element. So even an all-negative array has an answer (its max element), never 0.
Q4.Do I need to return the subarray itself or just the sum?
Just the sum for LeetCode 53. Returning the indices is a common follow-up — track the start/end as you reset.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Find the contiguous subarray with the largest sum. Brute force checks every subarray in O(n²). Kadane's algorithm does it in one pass: keep a running sum, and whenever that running sum goes negative, drop it and start fresh from the current element — because a negative prefix can only drag down whatever comes next. Track the best running sum seen along the way.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can move from the brute-force O(n²) subarray scan to the O(n) one-pass insight — and articulate *why* dropping a negative running prefix is always safe (the greedy/DP justification), not just memorise the two-liner.

Where candidates slip

Initialising the running and best sums to 0, which returns 0 on an all-negative array like [-3,-1,-2] instead of the correct -1; or comparing/resetting in the wrong order so a fresh start is missed.

How to stand out

Explain Kadane's as the duality of DP ('best subarray ending at i') and greedy ('discard a negative prefix'), handle the all-negative edge case explicitly, and mention the Divide & Conquer O(n log n) variant exists for the follow-up.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Sum Every Subarray	`O(n²)`	`O(1)`	Say it first to anchor the O(n²) baseline, then pivot to 'we can avoid recomputing sums by carrying a running total' — that transition leads straight to Kadane's.	Read
2	Kadane's Algorithm — One-Pass Running Sum (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'best subarray ending at each index' and explain the negative-prefix reset — don't just recite the two lines.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMax sum of a contiguous subarrayNeed just the obvious answer?First attemptOptimalExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Sum Every Subarray

TimeO(n²)SpaceO(1)

Say it first to anchor the O(n²) baseline, then pivot to 'we can avoid recomputing sums by carrying a running total' — that transition leads straight to Kadane's.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A subarray is fixed by its start and end index. How many (start, end) pairs are there, and how would you score each?

2Hint 2Explore hint

Fix a start i, then extend the end j rightward, maintaining a running sum so you don't re-add from scratch each time.

3Hint 3Explore hint

Track a global best across all (i, j). That's two nested loops with an O(1) running sum inside — O(n²) total.

A · Core idea

Enumerate every contiguous subarray and keep the largest sum. Fix a start index i, then sweep an end index j from i to the end, accumulating nums[j] into a running total and comparing it against the global best.

Why carry a running sum instead of re-summing. A naive triple loop (recomputing each subarray's sum from scratch) is O(n³). By keeping a sum that we extend as j advances, scoring each subarray costs O(1) and the whole thing drops to O(n²). It's worth saying this out loud — it shows you optimise inside a loop before throwing the whole approach away.

Why this is the honest first answer. It directly encodes the definition: 'try all contiguous subarrays, take the max'. It's obviously correct and a good warm-up to reason about, which is exactly what an interviewer wants to hear before the clever pass. For n = 10⁵ (the constraint) O(n²) is ~10¹⁰ operations and will time out — so we present it, state the cost, and improve.

Why it sets up Kadane's. Notice the inner loop already maintains 'the sum of the subarray ending at j that started at i'. Kadane's insight is that we don't need to try every start i independently — we can decide, in one pass, whether to keep extending the current run or to abandon it. That observation collapses the outer loop entirely.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [-2, 1, -3]

i=0

sums: -2, -2+1=-1, -1-3=-4

Statebest = -1

Final result1

C · Code with teaching comments

Reference implementation previewpublic 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++) {Explore the full code

solution.javaJava

Brute Force — Sum Every Subarray — reference

4 teaching notes

1
public int maxSubArray(int[] nums) {
2
    // Start below any real sum so all-negative arrays still register their max element.
3
    int best = Integer.MIN_VALUE;
4
    for (int i = 0; i < nums.length; i++) {
5
        // Reset the running total for each new start index i.
6
        int sum = 0;
7
        for (int j = i; j < nums.length; j++) {
8
            // Extend the current subarray by one element in O(1) — avoids the O(n³)
9
            // re-sum.
10
            sum += nums[j];
11
            // Every (i, j) pair is a candidate subarray; keep the largest sum seen.
12
            best = Math.max(best, sum);
13
        }
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

The brute force already contains the seed of the optimal: a running sum extended one element at a time. The only wasteful part is restarting that sum from every possible left endpoint. The leap to O(n) is realising you can decide on the fly when restarting helps, instead of trying all restarts.

ComplexityO(n²) time, O(1) space — There are about n²/2 subarrays; by carrying a running sum in the inner loop we score each in O(1), so the work is O(n²) time and O(1) extra space.

E · Edge cases and pitfalls5nums = [-3, -1, -2] — best starts at MIN_VALUE; the single-element subarray [-1] sets best = -1, which no longer run beats → returns -1.Explore edge cases

Edge cases handled

nums = [-3, -1, -2]best starts at MIN_VALUE; the single-element subarray [-1] sets best = -1, which no longer run beats → returns -1.
nums = [5]Single (i=0, j=0) subarray of sum 5 → returns 5.

Pitfalls

Initialising best to 0 — wrong on all-negative arrays.
Recomputing each subarray sum from scratch in a third loop — needlessly O(n³).
Presenting this as the solution — it TLEs at n = 10⁵; it's the warm-up, not the answer.

03.2

Approach 2 of 2 · Optimal

Kadane's Algorithm — One-Pass Running Sum (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'best subarray ending at each index' and explain the negative-prefix reset — don't just recite the two lines.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you know the best subarray sum ending exactly at index i-1. How does that help you compute the best sum ending at index i?

2Hint 2Explore hint

At index i you either extend the previous run (cur + nums[i]) or start a brand-new run at nums[i]. Which would you pick, and when?

3Hint 3Explore hint

If the previous running sum is negative, it only drags nums[i] down — so reset. Keep cur = max(nums[i], cur + nums[i]) and track best = max(best, cur).

A · Core idea

Walk the array once, maintaining cur = the largest sum of a subarray that ends at the current index, and best = the largest cur seen so far. At each element, cur = max(num, cur + num) and best = max(best, cur).

Why 'best ending here' is the right state. Any maximum subarray has to end somewhere. If, for every index, we know the best subarray that ends exactly there, then the overall answer is just the maximum of those per-index bests. So we reduce a 2D search (start, end) to a 1D scan: only the end index moves, and cur summarises the best choice of start for that end.

Why we reset when the prefix goes negative. The choice cur = max(num, cur + num) says: either glue num onto the run ending at the previous index, or throw that run away and begin fresh at num. Starting fresh wins exactly when cur + num < num, i.e. when cur < 0. The reasoning is airtight — if the sum accumulated so far is negative, it can only reduce the total of anything we extend it into, so the optimal subarray ending here would never include that negative prefix. Drop it.

Why `cur` and `best` are separate. cur is allowed to fall (and reset) as we move right; it tracks a local, end-anchored quantity. best is the high-water mark that never decreases. Conflating them — for example returning cur at the end — would report the sum of the last run instead of the largest run anywhere.

Why initialise to `nums[0]` and not 0. The subarray must be non-empty, and an all-negative array's answer is its least-negative element. Seeding cur = best = nums[0] and scanning from index 1 guarantees we never invent an empty (sum-0) subarray.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

num=4 (i=3)

prev cur was -2 → restart, cur = 4

-2

[0]

[1]

-3

[2]

i ↓

[3]

-1

[4]

[5]

[6]

-5

[7]

[8]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Kadane's Algorithm — One-Pass Running Sum (Optimal) — optimal

4 teaching notes

1
public int maxSubArray(int[] nums) {
2
    // Best subarray ending at index 0 is the element itself — seeds the recurrence
3
    // non-empty.
4
    int cur = nums[0];
5
    // Global answer starts at the first element, not 0 — this is the all-negative
6
    // safeguard.
7
    int best = nums[0];
8
    for (int i = 1; i < nums.length; i++) {
9
        // Extend the previous run or restart at nums[i]; restarting wins exactly when
10
        // the old cur was negative.
11
        cur = Math.max(nums[i], cur + nums[i]);
12
        // cur can dip and reset, but best only ever rises — keep them separate.
13
        best = Math.max(best, cur);
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

Kadane's is where DP and greedy shake hands. The DP view: cur[i] = max(nums[i], cur[i-1] + nums[i]) is a one-line recurrence for 'best subarray ending at i'. The greedy view: at each step you make the locally optimal choice to discard a negative prefix, and you can prove that local choice is globally optimal because a negative prefix never helps. Most candidates memorise the two lines; saying why the greedy discard is safe is what lands the signal.

ComplexityO(n) time, O(1) space — A single left-to-right pass doing O(1) work (two comparisons and an add) per element gives O(n) time, and we keep only two scalars (cur, best) so space is O(1).

E · Edge cases and pitfalls5nums = [-3, -1, -2] — cur restarts at each element (every prefix is negative); best tracks the max single element → -1.Explore edge cases

Edge cases handled

nums = [-3, -1, -2]cur restarts at each element (every prefix is negative); best tracks the max single element → -1.
nums = [5, 4, -1, 7, 8]cur never goes negative so it keeps extending; best ends at 23, the sum of the whole array.

Pitfalls

Seeding cur/best to 0 — returns 0 on all-negative input instead of the max element.
Returning cur instead of best — reports the last run, not the largest one.
Writing cur = cur + max(num, ...) or otherwise scrambling the max — the reset condition must compare num against cur + num.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxSubArray(int[] nums) { int cur = nums[0]; int best = nums[0]; for (int i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Zero-initialised sums on all-negative arrays

Starting best at 0 means a fully-negative array reports 0, but the subarray must be non-empty, so the answer is the largest (least negative) element.

Explore the code comparison

Don't write this

int cur = 0, best = 0;
for (int num : nums) {
    cur = Math.max(num, cur + num);
    best = Math.max(best, cur);
}
return best; // returns 0 on [-3,-1,-2]

Write this instead

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;

Returning cur instead of best

cur is the best subarray ending at the LAST index; the global maximum may have occurred earlier and been lost when cur reset.

Explore the code comparison

Don't write this

cur = best = nums[0]
for num in nums[1:]:
    cur = max(num, cur + num)
    best = max(best, cur)
return cur  # wrong — ignores earlier peaks

Write this instead

cur = best = nums[0]
for num in nums[1:]:
    cur = max(num, cur + num)
    best = max(best, cur)
return best

Wrong reset comparison

The reset must compare the bare element against the extended run. Reversing it (or adding before deciding) can keep a harmful negative prefix.

Explore the code comparison

Don't write this

cur = cur + nums[i];
if (cur < 0) cur = 0; // resets to 0, not nums[i] — drops a needed element

Write this instead

cur = Math.max(nums[i], cur + nums[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane's — running sum with negative-prefix reset

Code pattern to memorize

cur = max(num, cur + num)   # extend, or start fresh at num
best = max(best, cur)
# init: cur = best = nums[0]

Rules to remember

1Carry a running sum cur; at each element choose max(num, cur + num) — extend the previous subarray or restart at num.
2You restart precisely when `cur + num < num`, i.e. when the previous cur was negative — a negative prefix only hurts.
3Track best separately from cur; the running sum dips and resets, but best only ever climbs.
4Initialise both to nums[0], not 0 — an all-negative array must return its largest (least negative) element, and 0 would be wrong.
5It's DP and greedy at once: cur is 'best subarray ending here' (DP state), and discarding a negative prefix is the greedy local choice that's provably global.

Use this pattern when

Maximum / minimum sum (or product) of a *contiguous* subarray or substring window
A running accumulator where a negative (or otherwise harmful) prefix should be discarded
One-pass, O(1)-space optimisation over an obvious O(n²) subarray scan
'Best ending here' can be computed from 'best ending at the previous index' in O(1)

Choose another pattern when

Subarray need not be contiguous → it's a subsequence/knapsack problem, not Kadane's
You need the indices of *all* maximal subarrays → augment, or use a different scan
Elements can be reordered → sorting/greedy on values, contiguity no longer matters
Products with negatives flip signs → track both max and min (Maximum Product Subarray)

Interview takeaway

Kadane's is the canonical 'best-ending-here' scan: one running value, reset it the instant it stops helping, and remember the best you ever saw. The same shape — local DP state plus a greedy discard — reappears in Best Time to Buy/Sell Stock, Maximum Product Subarray, and Maximum Sum Circular Subarray.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Kadane's / 'best ending here' scan — keep a running value, reset it the moment a prefix stops helping, and remember the best ever seen. It's simultaneously a 1-line DP and a provable greedy; the same shape powers Maximum Product Subarray, Best Time to Buy/Sell Stock, and Maximum Sum Circular Subarray.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Product Subarray
Coming soon
Products flip sign on negatives — track both the running max AND min at each index.
Maximum Sum Circular Subarray
Coming soon
Answer is max(normal Kadane, total − min-subarray); special-case the all-negative array.
Best Time to Buy and Sell Stock
Coming soon
Kadane's on the daily price differences gives the max profit window.
Max Length of Subarray With Positive Product
Coming soon
Same running-state idea, but track lengths of positive- and negative-product runs.

Same pattern

Continue · Next problem

Climbing Stairs

mediumArraysLC #53Asked very often

Maximum Subarray (Kadane's)

LCPractice

Dynamic Programming · 1 of 44 · 8 min

Given an integer array nums, find the **contiguous** subarray (containing at least one number) which has the largest sum, and return its sum.

A subarray is a contiguous part of an array.

In plain English

Examples

Example 1

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Note: The subarray [4, -1, 2, 1] sums to 6 — the best contiguous run.

Example 2

Input: nums = [1]
Output: 1
Note: A single element is its own best subarray.

Example 3

Input: nums = [-3, -1, -2]
Output: -1
Note: All negative — the best you can do is the single largest element, -1.

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴
The subarray must contain at least one element
Elements may be negative, zero, or positive

Clarifying questions4First question: Does the subarray have to be contiguous?Explore questions

Q1.Does the subarray have to be contiguous?
Yes — that's the whole problem. If gaps were allowed you'd just sum all the positives; contiguity is what makes the running-sum reset necessary.
Q2.Can the array be all negative?
Yes. [-3, -1, -2] must return -1, the largest single element. This is why you can't initialise the answer to 0.
Q3.Is an empty subarray allowed?
No — at least one element. So even an all-negative array has an answer (its max element), never 0.
Q4.Do I need to return the subarray itself or just the sum?
Just the sum for LeetCode 53. Returning the indices is a common follow-up — track the start/end as you reset.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Initialising the running and best sums to 0, which returns 0 on an all-negative array like [-3,-1,-2] instead of the correct -1; or comparing/resetting in the wrong order so a fresh start is missed.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Sum Every Subarray	`O(n²)`	`O(1)`	Say it first to anchor the O(n²) baseline, then pivot to 'we can avoid recomputing sums by carrying a running total' — that transition leads straight to Kadane's.	Read
2	Kadane's Algorithm — One-Pass Running Sum (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want. Frame it as 'best subarray ending at each index' and explain the negative-prefix reset — don't just recite the two lines.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Sum Every Subarray

TimeO(n²)SpaceO(1)

Say it first to anchor the O(n²) baseline, then pivot to 'we can avoid recomputing sums by carrying a running total' — that transition leads straight to Kadane's.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A subarray is fixed by its start and end index. How many (start, end) pairs are there, and how would you score each?

2Hint 2Explore hint

Fix a start i, then extend the end j rightward, maintaining a running sum so you don't re-add from scratch each time.

3Hint 3Explore hint

Track a global best across all (i, j). That's two nested loops with an O(1) running sum inside — O(n²) total.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

nums = [-2, 1, -3]

i=0

sums: -2, -2+1=-1, -1-3=-4

Statebest = -1

Final result1

C · Code with teaching comments

solution.javaJava

Brute Force — Sum Every Subarray — reference

4 teaching notes

1
public int maxSubArray(int[] nums) {
2
    // Start below any real sum so all-negative arrays still register their max element.
3
    int best = Integer.MIN_VALUE;
4
    for (int i = 0; i < nums.length; i++) {
5
        // Reset the running total for each new start index i.
6
        int sum = 0;
7
        for (int j = i; j < nums.length; j++) {
8
            // Extend the current subarray by one element in O(1) — avoids the O(n³)
9
            // re-sum.
10
            sum += nums[j];
11
            // Every (i, j) pair is a candidate subarray; keep the largest sum seen.
12
            best = Math.max(best, sum);
13
        }
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n²) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(1) space — There are about n²/2 subarrays; by carrying a running sum in the inner loop we score each in O(1), so the work is O(n²) time and O(1) extra space.

E · Edge cases and pitfalls5nums = [-3, -1, -2] — best starts at MIN_VALUE; the single-element subarray [-1] sets best = -1, which no longer run beats → returns -1.Explore edge cases

Edge cases handled

nums = [-3, -1, -2]best starts at MIN_VALUE; the single-element subarray [-1] sets best = -1, which no longer run beats → returns -1.
nums = [5]Single (i=0, j=0) subarray of sum 5 → returns 5.

Pitfalls

Initialising best to 0 — wrong on all-negative arrays.
Recomputing each subarray sum from scratch in a third loop — needlessly O(n³).
Presenting this as the solution — it TLEs at n = 10⁵; it's the warm-up, not the answer.

03.2

Approach 2 of 2 · Optimal

Kadane's Algorithm — One-Pass Running Sum (Optimal)

TimeO(n)SpaceO(1)

The answer they want. Frame it as 'best subarray ending at each index' and explain the negative-prefix reset — don't just recite the two lines.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Suppose you know the best subarray sum ending exactly at index i-1. How does that help you compute the best sum ending at index i?

2Hint 2Explore hint

At index i you either extend the previous run (cur + nums[i]) or start a brand-new run at nums[i]. Which would you pick, and when?

3Hint 3Explore hint

If the previous running sum is negative, it only drags nums[i] down — so reset. Keep cur = max(nums[i], cur + nums[i]) and track best = max(best, cur).

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

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

Array state

num=4 (i=3)

prev cur was -2 → restart, cur = 4

-2

[0]

[1]

-3

[2]

i ↓

[3]

-1

[4]

[5]

[6]

-5

[7]

[8]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Kadane's Algorithm — One-Pass Running Sum (Optimal) — optimal

4 teaching notes

1
public int maxSubArray(int[] nums) {
2
    // Best subarray ending at index 0 is the element itself — seeds the recurrence
3
    // non-empty.
4
    int cur = nums[0];
5
    // Global answer starts at the first element, not 0 — this is the all-negative
6
    // safeguard.
7
    int best = nums[0];
8
    for (int i = 1; i < nums.length; i++) {
9
        // Extend the previous run or restart at nums[i]; restarting wins exactly when
10
        // the old cur was negative.
11
        cur = Math.max(nums[i], cur + nums[i]);
12
        // cur can dip and reset, but best only ever rises — keep them separate.
13
        best = Math.max(best, cur);
14
    }
15
    return best;
16
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.16 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5nums = [-3, -1, -2] — cur restarts at each element (every prefix is negative); best tracks the max single element → -1.Explore edge cases

Edge cases handled

nums = [-3, -1, -2]cur restarts at each element (every prefix is negative); best tracks the max single element → -1.
nums = [5, 4, -1, 7, 8]cur never goes negative so it keeps extending; best ends at 23, the sum of the whole array.

Pitfalls

Seeding cur/best to 0 — returns 0 on all-negative input instead of the max element.
Returning cur instead of best — reports the last run, not the largest one.
Writing cur = cur + max(num, ...) or otherwise scrambling the max — the reset condition must compare num against cur + num.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int maxSubArray(int[] nums) { int cur = nums[0]; int best = nums[0]; for (int i = 1; i < nums.length; i++) { cur = Math.max(nums[i], cur + nums[i]);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Zero-initialised sums on all-negative arrays

Starting best at 0 means a fully-negative array reports 0, but the subarray must be non-empty, so the answer is the largest (least negative) element.

Explore the code comparison

Don't write this

int cur = 0, best = 0;
for (int num : nums) {
    cur = Math.max(num, cur + num);
    best = Math.max(best, cur);
}
return best; // returns 0 on [-3,-1,-2]

Write this instead

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;

Returning cur instead of best

cur is the best subarray ending at the LAST index; the global maximum may have occurred earlier and been lost when cur reset.

Explore the code comparison

Don't write this

cur = best = nums[0]
for num in nums[1:]:
    cur = max(num, cur + num)
    best = max(best, cur)
return cur  # wrong — ignores earlier peaks

Write this instead

cur = best = nums[0]
for num in nums[1:]:
    cur = max(num, cur + num)
    best = max(best, cur)
return best

Wrong reset comparison

The reset must compare the bare element against the extended run. Reversing it (or adding before deciding) can keep a harmful negative prefix.

Explore the code comparison

Don't write this

cur = cur + nums[i];
if (cur < 0) cur = 0; // resets to 0, not nums[i] — drops a needed element

Write this instead

cur = Math.max(nums[i], cur + nums[i]);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Kadane's — running sum with negative-prefix reset

Code pattern to memorize

cur = max(num, cur + num)   # extend, or start fresh at num
best = max(best, cur)
# init: cur = best = nums[0]

Rules to remember

1Carry a running sum cur; at each element choose max(num, cur + num) — extend the previous subarray or restart at num.
2You restart precisely when `cur + num < num`, i.e. when the previous cur was negative — a negative prefix only hurts.
3Track best separately from cur; the running sum dips and resets, but best only ever climbs.
4Initialise both to nums[0], not 0 — an all-negative array must return its largest (least negative) element, and 0 would be wrong.
5It's DP and greedy at once: cur is 'best subarray ending here' (DP state), and discarding a negative prefix is the greedy local choice that's provably global.

Use this pattern when

Maximum / minimum sum (or product) of a *contiguous* subarray or substring window
A running accumulator where a negative (or otherwise harmful) prefix should be discarded
One-pass, O(1)-space optimisation over an obvious O(n²) subarray scan
'Best ending here' can be computed from 'best ending at the previous index' in O(1)

Choose another pattern when

Subarray need not be contiguous → it's a subsequence/knapsack problem, not Kadane's
You need the indices of *all* maximal subarrays → augment, or use a different scan
Elements can be reordered → sorting/greedy on values, contiguity no longer matters
Products with negatives flip signs → track both max and min (Maximum Product Subarray)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Maximum Product Subarray
Coming soon
Products flip sign on negatives — track both the running max AND min at each index.
Maximum Sum Circular Subarray
Coming soon
Answer is max(normal Kadane, total − min-subarray); special-case the all-negative array.
Best Time to Buy and Sell Stock
Coming soon
Kadane's on the daily price differences gives the max profit window.
Max Length of Subarray With Positive Product
Coming soon
Same running-state idea, but track lengths of positive- and negative-product runs.

Same pattern

Continue · Next problem

Climbing Stairs