Loading…

mediumDynamic ProgrammingFrequently asked

Max Array Sum

Q: How do you solve Max Array Sum using the Brute Force — Recurse Over Take / Skip approach?

When to use it: State it to expose the overlapping subproblems, then add memoization or tabulation to kill the exponential blowup. The most literal model: at every index decide independently to take or skip. If you take `a[i]`, you must jump to `i+2` because `i+1` is now forbidden. If you skip, you advance to `i+1` with no penalty. The answer from index `i` onward is the better of the two branches: `f(i) = max(a[i] + f(i+2), f(i+1))`. **Why two branches and nothing else.** The adjacency rule constrains only *immediate* neighbours. Once you decide about index `i`, the rest of the problem is the *same shape* on a shorter suffix — a smaller instance of Max Array Sum. That self-similarity is what makes it a DP problem rather than a greedy one. **Why greedy fails.** A tempting greedy is 'always take the larger of two neighbours'. It breaks on `[2, 1, 5, 8, 4]`: greedy might grab 8, blocking both 5 and 4, but the optimal `2 + 5 + 4 = 11` beats `1 + 8 = 9`. Local choices can't see the downstream cost, so you must compare full branches — hence recursion. **Why we don't ship this.** The recursion tree has ~`2ⁿ` nodes, but there are only `n` distinct arguments to `f`. The same `f(i)` is recomputed exponentially often. For `n = 10⁵` this never finishes. The fix is to *remember* each `f(i)` — memoization (top-down) or tabulation (bottom-up). Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve Max Array Sum using the Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python) approach?

When to use it: Show you can express the same recurrence both ways — caching a recursion (Java) or filling a table (Python) — and that they're equivalent in cost. Same recurrence, two equivalent implementations — and they're deliberately shown in different languages to highlight the trade-off. **Java — top-down memoization.** Keep the natural recursion from the brute force, but back it with a `memo` array. Before computing `f(i)`, check whether it's already cached; after computing, store it. Each `f(i)` is now evaluated once, so the `2ⁿ` tree collapses to `n` real computations. **Python — bottom-up tabulation.** Drop recursion entirely. Fill a `dp` array left to right: `dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i])`. Because `dp[i-1]` and `dp[i-2]` are computed before `dp[i]`, every value is ready when needed. The answer is `dp[n-1]`. **Why they're the same algorithm.** Both compute exactly the set of `n` subproblems once. Memoization computes them lazily, in the order the recursion happens to ask; tabulation computes them eagerly, in a fixed left-to-right order. Same time, same space, same answers. **Where they differ — and why it matters here.** Top-down recursion uses the call stack: for `n = 10⁵`, deep recursion can blow the stack. In **Python this is acute** — the default recursion limit is ~1000, so a top-down solution would raise `RecursionError` on large inputs unless you raise the limit. That's exactly why Python is shown bottom-up: tabulation uses a plain loop and no stack depth. **Java** tolerates deeper recursion and the JIT handles it well, so top-down reads cleanly there. The lesson: when `n` is large, prefer tabulation (or an explicit stack) in stack-limited languages. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Max Array Sum using the Rolling Variables — O(1) Space (Optimal) approach?

When to use it: The answer they want once tabulation is on the board. Phrase it as 'dp[i] only needs the last two values, so two scalars replace the array'. The tabulation never reaches further back than two cells, so storing the entire `dp` array wastes memory. Keep just two rolling variables: `prev2 = dp[i-2]` and `prev1 = dp[i-1]`. Compute `cur = max(prev1, prev2 + a[i], a[i])`, then slide: `prev2` becomes `prev1`, `prev1` becomes `cur`. **Why the three terms, restated for the scalar form.** `prev1` is the *skip* choice (carry the best up to `i-1`). `prev2 + a[i]` is the *take* choice (add `a[i]` to the best that excluded `i-1`). `a[i]` alone is the *fresh-start* choice — essential when `prev2` is negative, so a strong single element isn't dragged down by a bad prefix. **Why `prev2` starts at 0.** At `i = 1`, the term `prev2 + a[1]` should mean 'take `a[1]` with nothing before it', i.e. just `a[1]`. Seeding `prev2 = 0` makes that fall out automatically, and it equals the `a[i]` term — harmless overlap. **Why this is the version to ship.** Same `O(n)` time as tabulation but `O(1)` space, and no recursion stack to overflow — safe even at `n = 10⁵`. It's also the cleanest to state in an interview: two variables, one pass. **Reconstructing the chosen subset.** If asked *which* elements were picked, the O(1) trick loses that information — you'd keep the full `dp` array (or a parent/decision array) and walk backwards. Mention this trade-off: O(1) space gives the value, not the witness. Time complexity: O(n). Space complexity: O(1).

Dynamic Programming · 19 of 44 · 11 min

Given an array of integers, find the maximum sum of a subset such that no two chosen elements are adjacent in the array.

You may skip as many elements as you like; the only restriction is that you cannot pick two elements that sit next to each other. Elements may be negative, so the optimal subset is not simply 'all the positives'.

Return the maximum achievable sum.

In plain English

This is House Robber with a twist: you maximise a sum over a subset where adjacency is forbidden, but negatives mean 'take everything non-adjacent' is wrong. At each index you either take the element (and must have skipped its neighbour) or skip it — a two-way branch that yields a clean O(n) recurrence.

Examples

Example 1

Input: a = [3, 7, 4, 6, 5]
Output: 13
Note: Take 7 and 6 (indices 1 and 3) → 13. Also 3+4+... gives less. 7 and 6 are non-adjacent and maximal.

Example 2

Input: a = [-2, 1, 3, -4, 5]
Output: 8
Note: Take 3 and 5 (indices 2 and 4) → 8. The negatives are skipped entirely.

Example 3

Input: a = [2, 1, 5, 8, 4]
Output: 11
Note: Take 2, 5, 4 (indices 0, 2, 4) → 11, beating 1+8=9. Three non-adjacent picks win here.

Constraints

1 ≤ n ≤ 10⁵
-10⁴ ≤ a[i] ≤ 10⁴
Elements may be negative
The chosen subset may be empty in some variants; here the recurrence allows a single element to stand alone

Clarifying questions4First question: Can the array contain negative numbers?Explore questions

Q1.Can the array contain negative numbers?
Yes — that's the whole point of the `a[i]` term. With only positives this reduces to plain House Robber.
Q2.Does 'adjacent' mean adjacent in the array or adjacent in value?
Adjacent positions in the array — indices i and i-1. Values are irrelevant to adjacency.
Q3.Is the array circular (does the last element neighbour the first)?
No, it's linear. If it wrapped, you'd run the linear DP twice — that's House Robber II.
Q4.Must I pick at least one element?
The given recurrence lets a single element stand alone, so it naturally returns the best single value when all sums are poor. Confirm whether an empty subset (sum 0) is allowed.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Pick a subset with maximum sum where no two chosen elements are adjacent (you may skip freely). The recurrence is dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i]): skip i, take i on top of the best up to i-2, or start fresh at i. This is the House Robber pattern generalised to allow skipping and negatives. O(n) time, and O(1) space once you keep only the last two dp values.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you model 'no two adjacent' as a take-or-skip recurrence depending on dp[i-1] and dp[i-2], and whether you handle negatives by allowing an element to stand alone.

Where candidates slip

Dropping the `a[i]` (start-fresh) term, so a negative prefix drags down an otherwise good single element; or using dp[i-1] instead of dp[i-2] when taking i (which permits adjacency).

How to stand out

Name the House Robber pattern, derive the recurrence from the binary take/skip choice, then collapse the dp array to O(1) space with two rolling variables.

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 — Recurse Over Take / Skip	`O(2ⁿ)`	`O(n)`	State it to expose the overlapping subproblems, then add memoization or tabulation to kill the exponential blowup.	Read
2	Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python)	`O(n)`	`O(n)`	Show you can express the same recurrence both ways — caching a recursion (Java) or filling a table (Python) — and that they're equivalent in cost.	Read
3	Rolling Variables — O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want once tabulation is on the board. Phrase it as 'dp[i] only needs the last two values, so two scalars replace the array'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewAt index iTake a[i]?SkipTakeExplore 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 3

Brute Force — Recurse Over Take / Skip

TimeO(2ⁿ)SpaceO(n)

State it to expose the overlapping subproblems, then add memoization or tabulation to kill the exponential blowup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Stand at index i. You can either take a[i] — then the next allowed index is i+2 — or skip it and move to i+1. What's the best you can do from index i onward?

2Hint 2Explore hint

Write f(i) = max(a[i] + f(i+2), f(i+1)): take this element and jump two, or skip and step one.

3Hint 3Explore hint

This explores both branches at every index → 2ⁿ paths. Notice f(i) is recomputed many times for the same i — that's the cue for memoization.

A · Core idea

The most literal model: at every index decide independently to take or skip. If you take a[i], you must jump to i+2 because i+1 is now forbidden. If you skip, you advance to i+1 with no penalty. The answer from index i onward is the better of the two branches: f(i) = max(a[i] + f(i+2), f(i+1)).

Why two branches and nothing else. The adjacency rule constrains only immediate neighbours. Once you decide about index i, the rest of the problem is the same shape on a shorter suffix — a smaller instance of Max Array Sum. That self-similarity is what makes it a DP problem rather than a greedy one.

Why greedy fails. A tempting greedy is 'always take the larger of two neighbours'. It breaks on [2, 1, 5, 8, 4]: greedy might grab 8, blocking both 5 and 4, but the optimal 2 + 5 + 4 = 11 beats 1 + 8 = 9. Local choices can't see the downstream cost, so you must compare full branches — hence recursion.

Why we don't ship this. The recursion tree has ~`2ⁿnodes, but there are onlyndistinct arguments tof. The same f(i)is recomputed exponentially often. Forn = 10⁵this never finishes. The fix is to *remember* eachf(i)` — memoization (top-down) or tabulation (bottom-up).

B · Visual dry run

Interactive dry run

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

a = [3, 7, 4]

Interactive diagram

The recursion tree recomputes f(i)

f(2)

Active call / nodeSupporting contextReturned stateNot active

Notice f(2) appears on multiple branches — that repetition is the exponential cost.

Final result7

C · Code with teaching comments

Reference implementation previewpublic int maxSubsetSum(int[] a) { return f(a, 0); } private int f(int[] a, int i) {Explore the full code

solution.javaJava

Brute Force — Recurse Over Take / Skip — reference

4 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    return f(a, 0);
3
}
4
 
5
private int f(int[] a, int i) {
6
    // Past the end there's nothing to add — base case contributes 0.
7
    if (i >= a.length) return 0;
8
    // Take a[i], then jump to i+2 because i+1 is now forbidden.
9
    int take = a[i] + f(a, i + 2);
10
    // Skip a[i] and move one step right with no constraint.
11
    int skip = f(a, i + 1);
12
    // The best of the two branches — this comparison is why greedy can't replace it.
13
    return Math.max(take, skip);
14
}

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

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

The exponential cost comes entirely from recomputing the same f(i) over and over. There are only n distinct subproblems, so caching each one collapses 2ⁿ work down to O(n). Spotting 'few distinct subproblems, recomputed often' is the universal trigger for dynamic programming.

ComplexityO(2ⁿ) time, O(n) space — Each call spawns two recursive calls (take / skip), forming a binary tree of depth n → roughly 2ⁿ calls. Recursion depth is O(n) for the call stack.

E · Edge cases and pitfalls3Recursing to i+1 after taking a[i] — that permits adjacency and is wrong.Explore edge cases

Pitfalls

Recursing to i+1 after taking a[i] — that permits adjacency and is wrong.
Forgetting the base case, causing infinite recursion or index errors.
Running it on large n — 2ⁿ never returns; you must memoize or tabulate.

03.2

Approach 2 of 3

Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python)

TimeO(n)SpaceO(n)

Show you can express the same recurrence both ways — caching a recursion (Java) or filling a table (Python) — and that they're equivalent in cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are only n distinct values of f(i). Store each one the first time you compute it so the second request is a lookup, not a recomputation.

2Hint 2Explore hint

Top-down: keep the recursion but cache results in an array indexed by i. Bottom-up: drop recursion and fill dp[0], dp[1], ... in order using dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i]).

3Hint 3Explore hint

Both visit each subproblem once → O(n) time and O(n) space. The only real difference is recursion-stack risk (top-down) versus an explicit loop (bottom-up).

A · Core idea

Same recurrence, two equivalent implementations — and they're deliberately shown in different languages to highlight the trade-off.

Java — top-down memoization. Keep the natural recursion from the brute force, but back it with a memo array. Before computing f(i), check whether it's already cached; after computing, store it. Each f(i) is now evaluated once, so the 2ⁿ tree collapses to n real computations.

Python — bottom-up tabulation. Drop recursion entirely. Fill a dp array left to right: dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i]). Because dp[i-1] and dp[i-2] are computed before dp[i], every value is ready when needed. The answer is dp[n-1].

Why they're the same algorithm. Both compute exactly the set of n subproblems once. Memoization computes them lazily, in the order the recursion happens to ask; tabulation computes them eagerly, in a fixed left-to-right order. Same time, same space, same answers.

Where they differ — and why it matters here. Top-down recursion uses the call stack: for n = 10⁵, deep recursion can blow the stack. In Python this is acute — the default recursion limit is ~1000, so a top-down solution would raise RecursionError on large inputs unless you raise the limit. That's exactly why Python is shown bottom-up: tabulation uses a plain loop and no stack depth. Java tolerates deeper recursion and the JIT handles it well, so top-down reads cleanly there. The lesson: when n is large, prefer tabulation (or an explicit stack) in stack-limited languages.

B · Visual dry run

Interactive dry run

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

a = [3, 7, 4, 6, 5]

Array state

i=1

dp[1] = max(3, 7) = 7

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result13

C · Code with teaching comments

Reference implementation previewpublic int maxSubsetSum(int[] a) { Integer[] memo = new Integer[a.length]; return f(a, 0, memo); } Explore the full code

solution.javaJava

Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python) — reference

4 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    // null marks 'not computed yet'; a primitive int[] couldn't distinguish 0 from
3
    // unset.
4
    Integer[] memo = new Integer[a.length];
5
    return f(a, 0, memo);
6
}
7
 
8
private int f(int[] a, int i, Integer[] memo) {
9
    if (i >= a.length) return 0;
10
    // Cache hit — return immediately instead of recomputing the subtree.
11
    if (memo[i] != null) return memo[i];
12
    // Take branch jumps two indices to respect adjacency.
13
    int take = a[i] + f(a, i + 2, memo);
14
    int skip = f(a, i + 1, memo);
15
    // Store before returning so each i is computed exactly once — turns 2ⁿ into n.
16
    return memo[i] = Math.max(take, skip);
17
}

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

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

Memoization and tabulation are two views of one DP: lazy versus eager evaluation of the same subproblem set. Reach for top-down when the recurrence is easier to write recursively, and bottom-up when recursion depth (especially in Python) would overflow the stack. Knowing both — and when each fails — is what separates a memorised solution from an understood one.

ComplexityO(n) time, O(n) space — Each of the n subproblems is solved exactly once and cached, so total work is O(n). The cache (memo array or dp table) holds n entries → O(n) space. Top-down also uses O(n) call-stack depth.

E · Edge cases and pitfalls3In Java, using int[] for the memo can't tell 'unset' from a real 0 — use Integer[] with null.Explore edge cases

Pitfalls

In Java, using int[] for the memo can't tell 'unset' from a real 0 — use Integer[] with null.
In Python, writing this top-down risks RecursionError at n = 10⁵ — tabulate or raise the recursion limit.
Forgetting dp[1] = max(a[0], a[1]); setting dp[1] = a[1] allows skipping a better a[0].

03.3

Approach 3 of 3 · Optimal

Rolling Variables — O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The answer they want once tabulation is on the board. Phrase it as 'dp[i] only needs the last two values, so two scalars replace the array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i] depends only on dp[i-1] and dp[i-2]. Do you ever read anything older?

2Hint 2Explore hint

Replace the whole dp array with two variables — prev1 (dp[i-1]) and prev2 (dp[i-2]) — and slide them forward each step.

3Hint 3Explore hint

Initialise prev2 = 0 and prev1 = a[0]. Each step: cur = max(prev1, prev2 + a[i], a[i]); then prev2 = prev1, prev1 = cur.

A · Core idea

The tabulation never reaches further back than two cells, so storing the entire dp array wastes memory. Keep just two rolling variables: prev2 = dp[i-2] and prev1 = dp[i-1]. Compute cur = max(prev1, prev2 + a[i], a[i]), then slide: prev2 becomes prev1, prev1 becomes cur.

Why the three terms, restated for the scalar form. prev1 is the skip choice (carry the best up to i-1). prev2 + a[i] is the take choice (add a[i] to the best that excluded i-1). a[i] alone is the fresh-start choice — essential when prev2 is negative, so a strong single element isn't dragged down by a bad prefix.

Why `prev2` starts at 0. At i = 1, the term prev2 + a[1] should mean 'take a[1] with nothing before it', i.e. just a[1]. Seeding prev2 = 0 makes that fall out automatically, and it equals the a[i] term — harmless overlap.

Why this is the version to ship. Same O(n) time as tabulation but O(1) space, and no recursion stack to overflow — safe even at n = 10⁵. It's also the cleanest to state in an interview: two variables, one pass.

Reconstructing the chosen subset. If asked which elements were picked, the O(1) trick loses that information — you'd keep the full dp array (or a parent/decision array) and walk backwards. Mention this trade-off: O(1) space gives the value, not the witness.

B · Visual dry run

Interactive dry run

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

a = [2, 1, 5, 8, 4]

Array state

i=1

cur = max(2, 1, 1) = 2 → prev1=2

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result11

C · Code with teaching comments

solution.javaJava

Rolling Variables — O(1) Space (Optimal) — optimal

5 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    // dp[i-2] seed; 0 makes prev2 + a[1] reduce to a[1] at the first step.
3
    int prev2 = 0;
4
    // dp[0] is just the first element — best over a one-element prefix.
5
    int prev1 = a[0];
6
    for (int i = 1; i < a.length; i++) {
7
        // Skip (prev1), take (prev2 + a[i]), or start fresh (a[i]) — the full
8
        // recurrence in one line.
9
        int cur = Math.max(prev1, Math.max(prev2 + a[i], a[i]));
10
        // Slide the window: old prev1 becomes the new prev2.
11
        prev2 = prev1;
12
        prev1 = cur;
13
    }
14
    // After the loop prev1 holds dp[n-1], the answer.
15
    return prev1;
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

A recurrence whose window reaches back a fixed number of cells (here two) can always shed its array for that many scalars. This is the same compression that turns Fibonacci and Climbing Stairs from O(n) space into O(1) — recognise the bounded look-back and the optimisation is automatic.

ComplexityO(n) time, O(1) space — A single pass over n elements with constant work per step → O(n) time. Only two scalars are retained regardless of n → O(1) space.

E · Edge cases and pitfalls6a = [5] — Loop never runs; prev1 = a[0] = 5 is returned. Single element is its own answer.Explore edge cases

Edge cases handled

a = [5]Loop never runs; prev1 = a[0] = 5 is returned. Single element is its own answer.
a = [-1, -2, -3]Every take term is negative; cur tracks the least-bad single element → returns -1. The a[i] term keeps it from compounding negatives.
a = [1, 2, 3]i=1: max(1,2,2)=2; i=2: max(2, 1+3, 3)=4 → returns 4 (take 1 and 3). Adjacency between 2 and 3 correctly forbidden.

Pitfalls

Dropping the a[i] term — negative prev2 then forces a worse sum than taking the element alone.
Using prev1 (dp[i-1]) instead of prev2 in the take branch — that allows adjacent picks.
Trying to recover the chosen indices from O(1) space — you need the full dp array for that.

Practice

Try the solution yourself

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

Editable code previewpublic int maxSubsetSum(int[] a) { int prev2 = 0; int prev1 = a[0]; for (int i = 1; i < a.length; i++) { int cur = Math.max(prev1, Math.max(prev2 + a[i], a[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.

Forgetting the start-fresh term

On [-5, 10], taking 10 atop dp[i-2] = -5 gives 5, but 10 alone is better. Without the a[i] term you'd report 5 instead of 10.

Explore the code comparison

Don't write this

cur = max(prev1, prev2 + a[i])

Write this instead

cur = max(prev1, prev2 + a[i], a[i])

Taking on dp[i-1] instead of dp[i-2]

Adding a[i] to dp[i-1] lets index i pair with index i-1 — exactly the adjacency the problem forbids.

Explore the code comparison

Don't write this

int cur = Math.max(prev1, prev1 + a[i]);  // prev1 = dp[i-1]: adjacency allowed

Write this instead

int cur = Math.max(prev1, Math.max(prev2 + a[i], a[i]));  // prev2 = dp[i-2]

Top-down recursion in Python at scale

Python's default recursion limit (~1000) overflows at n = 10⁵. Tabulation uses a loop and has no such limit.

Explore the code comparison

Don't write this

def f(i):
    if i >= len(a): return 0
    return max(a[i] + f(i + 2), f(i + 1))  # RecursionError for large n

Write this instead

for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + a[i], a[i])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Non-adjacent selection DP (House Robber family)

Code pattern to memorize

dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i])
prev2, prev1 = 0, a[0]
for i in 1..n-1:
    cur = max(prev1, prev2 + a[i], a[i])
    prev2, prev1 = prev1, cur
return prev1

Rules to remember

1At each index you have exactly two choices: take it (then skip the neighbour) or skip it. That binary choice is the DP.
2The third term a[i] (start fresh) matters because negatives in dp[i-2] can make taking the element alone better than adding it to a worse prefix.
3Only the last two dp values feed the next one → collapse the array to two rolling variables for O(1) space.
4Adjacent means index i and i-1; skipping more than one in a row is always allowed.
5Initialise prev2 = 0 so dp[i-2] + a[i] at i = 1 correctly reduces to just a[i].

Use this pattern when

Choose a subset maximising/minimising a value with a 'no two adjacent' constraint
Linear sequence where taking one item forbids its immediate neighbour
House Robber / scheduling-with-cooldown shaped problems
You can skip arbitrarily many elements (unlike fixed-window problems)

Choose another pattern when

Adjacency wraps around a circle → House Robber II (run the linear DP twice)
Contiguous subarray required, not a subset → Kadane's algorithm
No adjacency constraint at all → just sum the positives
2D grid adjacency → grid DP, not this 1D recurrence

Interview takeaway

When taking an element forbids its neighbour, the answer at each position depends only on the answers two and one steps back. Recognise that and you've solved the whole House Robber family — including this skipping/negative variant — with two variables.

Continue

Transfer the pattern to another problem

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

Transferable patternCanonical non-adjacent selection DP (House Robber family). Whenever choosing an element forbids its neighbour, the state two steps back plus one step back determines the answer — collapse to two scalars for O(1) space. Same shape as House Robber, Delete and Earn, and cooldown-stock problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

House Robber
Positives only — the same recurrence without needing the start-fresh term.
House Robber II
Circular array — run the linear DP twice, once excluding the first house and once the last.
Delete and Earn
Coming soon
Bucket values into counts, then it's House Robber on the value axis.
Maximum Subarray
Coming soon
Contiguous (not subset) — Kadane's, the contrast case for the anti-signal.

Same pattern

←

Triangle

Continue · Next problem

The Coin Change Problem

mediumDynamic ProgrammingFrequently asked

Max Array Sum

Dynamic Programming · 19 of 44 · 11 min

Given an array of integers, find the maximum sum of a subset such that no two chosen elements are adjacent in the array.

Return the maximum achievable sum.

In plain English

Examples

Example 1

Input: a = [3, 7, 4, 6, 5]
Output: 13
Note: Take 7 and 6 (indices 1 and 3) → 13. Also 3+4+... gives less. 7 and 6 are non-adjacent and maximal.

Example 2

Input: a = [-2, 1, 3, -4, 5]
Output: 8
Note: Take 3 and 5 (indices 2 and 4) → 8. The negatives are skipped entirely.

Example 3

Input: a = [2, 1, 5, 8, 4]
Output: 11
Note: Take 2, 5, 4 (indices 0, 2, 4) → 11, beating 1+8=9. Three non-adjacent picks win here.

Constraints

1 ≤ n ≤ 10⁵
-10⁴ ≤ a[i] ≤ 10⁴
Elements may be negative
The chosen subset may be empty in some variants; here the recurrence allows a single element to stand alone

Clarifying questions4First question: Can the array contain negative numbers?Explore questions

Q1.Can the array contain negative numbers?
Yes — that's the whole point of the `a[i]` term. With only positives this reduces to plain House Robber.
Q2.Does 'adjacent' mean adjacent in the array or adjacent in value?
Adjacent positions in the array — indices i and i-1. Values are irrelevant to adjacency.
Q3.Is the array circular (does the last element neighbour the first)?
No, it's linear. If it wrapped, you'd run the linear DP twice — that's House Robber II.
Q4.Must I pick at least one element?
The given recurrence lets a single element stand alone, so it naturally returns the best single value when all sums are poor. Confirm whether an empty subset (sum 0) is allowed.

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

Whether you model 'no two adjacent' as a take-or-skip recurrence depending on dp[i-1] and dp[i-2], and whether you handle negatives by allowing an element to stand alone.

Where candidates slip

Dropping the `a[i]` (start-fresh) term, so a negative prefix drags down an otherwise good single element; or using dp[i-1] instead of dp[i-2] when taking i (which permits adjacency).

How to stand out

Name the House Robber pattern, derive the recurrence from the binary take/skip choice, then collapse the dp array to O(1) space with two rolling variables.

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 — Recurse Over Take / Skip	`O(2ⁿ)`	`O(n)`	State it to expose the overlapping subproblems, then add memoization or tabulation to kill the exponential blowup.	Read
2	Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python)	`O(n)`	`O(n)`	Show you can express the same recurrence both ways — caching a recursion (Java) or filling a table (Python) — and that they're equivalent in cost.	Read
3	Rolling Variables — O(1) Space (Optimal)Optimal	`O(n)`	`O(1)`	The answer they want once tabulation is on the board. Phrase it as 'dp[i] only needs the last two values, so two scalars replace the array'.	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 3

Brute Force — Recurse Over Take / Skip

TimeO(2ⁿ)SpaceO(n)

State it to expose the overlapping subproblems, then add memoization or tabulation to kill the exponential blowup.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Stand at index i. You can either take a[i] — then the next allowed index is i+2 — or skip it and move to i+1. What's the best you can do from index i onward?

2Hint 2Explore hint

Write f(i) = max(a[i] + f(i+2), f(i+1)): take this element and jump two, or skip and step one.

3Hint 3Explore hint

This explores both branches at every index → 2ⁿ paths. Notice f(i) is recomputed many times for the same i — that's the cue for memoization.

A · Core idea

B · Visual dry run

Interactive dry run

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

a = [3, 7, 4]

Interactive diagram

The recursion tree recomputes f(i)

f(2)

Active call / nodeSupporting contextReturned stateNot active

Notice f(2) appears on multiple branches — that repetition is the exponential cost.

Final result7

C · Code with teaching comments

Reference implementation previewpublic int maxSubsetSum(int[] a) { return f(a, 0); } private int f(int[] a, int i) {Explore the full code

solution.javaJava

Brute Force — Recurse Over Take / Skip — reference

4 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    return f(a, 0);
3
}
4
 
5
private int f(int[] a, int i) {
6
    // Past the end there's nothing to add — base case contributes 0.
7
    if (i >= a.length) return 0;
8
    // Take a[i], then jump to i+2 because i+1 is now forbidden.
9
    int take = a[i] + f(a, i + 2);
10
    // Skip a[i] and move one step right with no constraint.
11
    int skip = f(a, i + 1);
12
    // The best of the two branches — this comparison is why greedy can't replace it.
13
    return Math.max(take, skip);
14
}

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

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

ComplexityO(2ⁿ) time, O(n) space — Each call spawns two recursive calls (take / skip), forming a binary tree of depth n → roughly 2ⁿ calls. Recursion depth is O(n) for the call stack.

E · Edge cases and pitfalls3Recursing to i+1 after taking a[i] — that permits adjacency and is wrong.Explore edge cases

Pitfalls

Recursing to i+1 after taking a[i] — that permits adjacency and is wrong.
Forgetting the base case, causing infinite recursion or index errors.
Running it on large n — 2ⁿ never returns; you must memoize or tabulate.

03.2

Approach 2 of 3

Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python)

TimeO(n)SpaceO(n)

Show you can express the same recurrence both ways — caching a recursion (Java) or filling a table (Python) — and that they're equivalent in cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are only n distinct values of f(i). Store each one the first time you compute it so the second request is a lookup, not a recomputation.

2Hint 2Explore hint

Top-down: keep the recursion but cache results in an array indexed by i. Bottom-up: drop recursion and fill dp[0], dp[1], ... in order using dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i]).

3Hint 3Explore hint

Both visit each subproblem once → O(n) time and O(n) space. The only real difference is recursion-stack risk (top-down) versus an explicit loop (bottom-up).

A · Core idea

Same recurrence, two equivalent implementations — and they're deliberately shown in different languages to highlight the trade-off.

B · Visual dry run

Interactive dry run

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

a = [3, 7, 4, 6, 5]

Array state

i=1

dp[1] = max(3, 7) = 7

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result13

C · Code with teaching comments

Reference implementation previewpublic int maxSubsetSum(int[] a) { Integer[] memo = new Integer[a.length]; return f(a, 0, memo); } Explore the full code

solution.javaJava

Top-Down Memoization (Java) vs Bottom-Up Tabulation (Python) — reference

4 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    // null marks 'not computed yet'; a primitive int[] couldn't distinguish 0 from
3
    // unset.
4
    Integer[] memo = new Integer[a.length];
5
    return f(a, 0, memo);
6
}
7
 
8
private int f(int[] a, int i, Integer[] memo) {
9
    if (i >= a.length) return 0;
10
    // Cache hit — return immediately instead of recomputing the subtree.
11
    if (memo[i] != null) return memo[i];
12
    // Take branch jumps two indices to respect adjacency.
13
    int take = a[i] + f(a, i + 2, memo);
14
    int skip = f(a, i + 1, memo);
15
    // Store before returning so each i is computed exactly once — turns 2ⁿ into n.
16
    return memo[i] = Math.max(take, skip);
17
}

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

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

E · Edge cases and pitfalls3In Java, using int[] for the memo can't tell 'unset' from a real 0 — use Integer[] with null.Explore edge cases

Pitfalls

In Java, using int[] for the memo can't tell 'unset' from a real 0 — use Integer[] with null.
In Python, writing this top-down risks RecursionError at n = 10⁵ — tabulate or raise the recursion limit.
Forgetting dp[1] = max(a[0], a[1]); setting dp[1] = a[1] allows skipping a better a[0].

03.3

Approach 3 of 3 · Optimal

Rolling Variables — O(1) Space (Optimal)

TimeO(n)SpaceO(1)

The answer they want once tabulation is on the board. Phrase it as 'dp[i] only needs the last two values, so two scalars replace the array'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Look at the recurrence: dp[i] depends only on dp[i-1] and dp[i-2]. Do you ever read anything older?

2Hint 2Explore hint

Replace the whole dp array with two variables — prev1 (dp[i-1]) and prev2 (dp[i-2]) — and slide them forward each step.

3Hint 3Explore hint

Initialise prev2 = 0 and prev1 = a[0]. Each step: cur = max(prev1, prev2 + a[i], a[i]); then prev2 = prev1, prev1 = cur.

A · Core idea

B · Visual dry run

Interactive dry run

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

a = [2, 1, 5, 8, 4]

Array state

i=1

cur = max(2, 1, 1) = 2 → prev1=2

[0]

i ↓

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result11

C · Code with teaching comments

solution.javaJava

Rolling Variables — O(1) Space (Optimal) — optimal

5 teaching notes

1
public int maxSubsetSum(int[] a) {
2
    // dp[i-2] seed; 0 makes prev2 + a[1] reduce to a[1] at the first step.
3
    int prev2 = 0;
4
    // dp[0] is just the first element — best over a one-element prefix.
5
    int prev1 = a[0];
6
    for (int i = 1; i < a.length; i++) {
7
        // Skip (prev1), take (prev2 + a[i]), or start fresh (a[i]) — the full
8
        // recurrence in one line.
9
        int cur = Math.max(prev1, Math.max(prev2 + a[i], a[i]));
10
        // Slide the window: old prev1 becomes the new prev2.
11
        prev2 = prev1;
12
        prev1 = cur;
13
    }
14
    // After the loop prev1 holds dp[n-1], the answer.
15
    return prev1;
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 — A single pass over n elements with constant work per step → O(n) time. Only two scalars are retained regardless of n → O(1) space.

E · Edge cases and pitfalls6a = [5] — Loop never runs; prev1 = a[0] = 5 is returned. Single element is its own answer.Explore edge cases

Edge cases handled

a = [5]Loop never runs; prev1 = a[0] = 5 is returned. Single element is its own answer.
a = [-1, -2, -3]Every take term is negative; cur tracks the least-bad single element → returns -1. The a[i] term keeps it from compounding negatives.
a = [1, 2, 3]i=1: max(1,2,2)=2; i=2: max(2, 1+3, 3)=4 → returns 4 (take 1 and 3). Adjacency between 2 and 3 correctly forbidden.

Pitfalls

Dropping the a[i] term — negative prev2 then forces a worse sum than taking the element alone.
Using prev1 (dp[i-1]) instead of prev2 in the take branch — that allows adjacent picks.
Trying to recover the chosen indices from O(1) space — you need the full dp array for that.

Practice

Try the solution yourself

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

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.

Forgetting the start-fresh term

On [-5, 10], taking 10 atop dp[i-2] = -5 gives 5, but 10 alone is better. Without the a[i] term you'd report 5 instead of 10.

Explore the code comparison

Don't write this

cur = max(prev1, prev2 + a[i])

Write this instead

cur = max(prev1, prev2 + a[i], a[i])

Taking on dp[i-1] instead of dp[i-2]

Adding a[i] to dp[i-1] lets index i pair with index i-1 — exactly the adjacency the problem forbids.

Explore the code comparison

Don't write this

int cur = Math.max(prev1, prev1 + a[i]);  // prev1 = dp[i-1]: adjacency allowed

Write this instead

int cur = Math.max(prev1, Math.max(prev2 + a[i], a[i]));  // prev2 = dp[i-2]

Top-down recursion in Python at scale

Python's default recursion limit (~1000) overflows at n = 10⁵. Tabulation uses a loop and has no such limit.

Explore the code comparison

Don't write this

def f(i):
    if i >= len(a): return 0
    return max(a[i] + f(i + 2), f(i + 1))  # RecursionError for large n

Write this instead

for i in range(2, n):
    dp[i] = max(dp[i - 1], dp[i - 2] + a[i], a[i])

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Non-adjacent selection DP (House Robber family)

Code pattern to memorize

dp[i] = max(dp[i-1], dp[i-2] + a[i], a[i])
prev2, prev1 = 0, a[0]
for i in 1..n-1:
    cur = max(prev1, prev2 + a[i], a[i])
    prev2, prev1 = prev1, cur
return prev1

Rules to remember

1At each index you have exactly two choices: take it (then skip the neighbour) or skip it. That binary choice is the DP.
2The third term a[i] (start fresh) matters because negatives in dp[i-2] can make taking the element alone better than adding it to a worse prefix.
3Only the last two dp values feed the next one → collapse the array to two rolling variables for O(1) space.
4Adjacent means index i and i-1; skipping more than one in a row is always allowed.
5Initialise prev2 = 0 so dp[i-2] + a[i] at i = 1 correctly reduces to just a[i].

Use this pattern when

Choose a subset maximising/minimising a value with a 'no two adjacent' constraint
Linear sequence where taking one item forbids its immediate neighbour
House Robber / scheduling-with-cooldown shaped problems
You can skip arbitrarily many elements (unlike fixed-window problems)

Choose another pattern when

Adjacency wraps around a circle → House Robber II (run the linear DP twice)
Contiguous subarray required, not a subset → Kadane's algorithm
No adjacency constraint at all → just sum the positives
2D grid adjacency → grid DP, not this 1D recurrence

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

House Robber
Positives only — the same recurrence without needing the start-fresh term.
House Robber II
Circular array — run the linear DP twice, once excluding the first house and once the last.
Delete and Earn
Coming soon
Bucket values into counts, then it's House Robber on the value axis.
Maximum Subarray
Coming soon
Contiguous (not subset) — Kadane's, the contrast case for the anti-signal.

Same pattern

←

Triangle

Continue · Next problem

The Coin Change Problem