Largest sum with no two chosen positions adjacent
Medium · Target 15 minutes · Dynamic programming· Type asked at
Optiver
Google
Morgan Stanley
Given an array nums of non-negative integers, choose a subset of positions
such that no two chosen positions are adjacent, and return the largest possible sum of the chosen
values. Choosing nothing is allowed, so the answer is never negative.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 2, 3, 1] | 4 | Positions 0 and 2: 1 + 3. |
nums = [2, 7, 9, 3, 1] | 12 | Positions 0, 2 and 4: 2 + 9 + 1. Taking 7 and 3 gives only 10. |
nums = [4, 1, 1, 4, 2, 1] | 9 | Positions 0, 3 and 5. |
Constraints
- 1 ≤ n ≤ 10⁵
- 0 ≤ nums[i] ≤ 10⁴
Hints
Hint 1
Greedy fails. Taking the largest value first breaks on [2, 7, 9, 3, 1], where the greedy choice of 9 then blocks nothing useful, but on [5, 6, 5] it blocks both fives.
Hint 2
Think about the last position only. Either you take it or you do not, and each choice leaves a smaller version of the same problem.
Hint 3
If you take position i you cannot have taken i−1, so you add nums[i] to the best answer up to i−2. If you skip it, you keep the best answer up to i−1.
Hint 4
That recurrence only ever looks two steps back, so the whole table collapses into two variables.
Where people lose marks
- Reaching for greedy. It survives the first example and dies on the second, which is exactly how it gets through a first-round screen and fails the on-site.
- Assuming the chosen positions must alternate. On [5, 1, 1, 5] the answer takes positions 0 and 3, which are three apart.
- Initialising the two carried values to nums[0] and nums[1]. It works only if n ≥ 2, and the off-by-one is easy to get wrong. Initialise both to 0 and let the loop handle every position uniformly.
- Writing the O(n)-space table and stopping there. It is correct, and leaving the O(1) version unsaid costs you the follow-up.
Dry run on [4,1,1,4,2,1]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8nums401112432415best[i-2]0best[i-1]0
Two carried values: the best answer one position back and the best two positions back. Both start at zero, which is the empty selection.
-
Step 2 / 8nums40i1112432415take4skip0best4
Position 0, value 4. Take it: 0 + 4 = 4. Skip it: 0. Taking wins, so best is 4.
-
Step 3 / 8nums4011i12432415take1skip4best4
Position 1, value 1. Take it: 0 + 1 = 1. Skip it: 4. Skipping wins, so best is 4.
-
Step 4 / 8nums401112i432415take5skip4best5
Position 2, value 1. Take it: 4 + 1 = 5. Skip it: 4. Taking wins, so best is 5.
-
Step 5 / 8nums40111243i2415take8skip5best8
Position 3, value 4. Take it: 4 + 4 = 8. Skip it: 5. Taking wins, so best is 8.
-
Step 6 / 8nums4011124324i15take7skip8best8
Position 4, value 2. Take it: 5 + 2 = 7. Skip it: 8. Skipping wins, so best is 8.
-
Step 7 / 8nums401112432415itake9skip8best9
Position 5, value 1. Take it: 8 + 1 = 9. Skip it: 8. Taking wins, so best is 9.
-
Step 8 / 8nums401112432415answer9
Every position has been considered. The answer is 9.
How to think about it
Interview lists usually call this House Robber: a street of houses, each holding some cash, where robbing two neighbours sets off the alarm. The story changes nothing about the mathematics.
Let best[i] be the largest valid sum using only the first i
positions. At position i there are exactly two options, and they are exhaustive:
- Take it. Then
i − 1is unavailable, so the rest of the sum is the best answer up toi − 2:nums[i] + best[i-2]. - Skip it. Then nothing new is blocked and the answer is
best[i-1].
So best[i] = max(best[i-1], nums[i] + best[i-2]), with best[-1] = 0
and best[-2] = 0. That is the entire algorithm.
The recurrence reaches back two positions and no further, so there is no reason to keep the whole table. Carry two numbers — the answer one step back and the answer two steps back — and roll them forward. The space drops from O(n) to O(1) and the code gets shorter, which is unusual enough to be worth pointing out.
The reason this is the right first dynamic programming problem is that the recurrence is forced. You are not choosing a clever state; you are writing down the only two things that can happen at position i, and the subproblem structure falls out.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_non_adjacent(nums):
prev2 = prev1 = 0 # best up to i-2, best up to i-1
for value in nums:
prev2, prev1 = prev1, max(prev1, prev2 + value)
return prev1#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& nums) {
long long prev2 = 0, prev1 = 0; // best up to i-2, best up to i-1
for (int value : nums) {
const long long best = std::max(prev1, prev2 + value);
prev2 = prev1;
prev1 = best;
}
return prev1;
}class Solution {
public long maxNonAdjacent(int[] nums) {
long prev2 = 0, prev1 = 0; // best up to i-2, best up to i-1
for (int value : nums) {
long best = Math.max(prev1, prev2 + value);
prev2 = prev1;
prev1 = best;
}
return prev1;
}
}function maxNonAdjacent(nums) {
let prev2 = 0, prev1 = 0; // best up to i-2, best up to i-1
for (const value of nums) {
const best = Math.max(prev1, prev2 + value);
prev2 = prev1;
prev1 = best;
}
return prev1;
}fn solve(nums: &[i64]) -> i64 {
let (mut prev2, mut prev1) = (0i64, 0i64); // best up to i-2, best up to i-1
for &value in nums {
let best = prev1.max(prev2 + value);
prev2 = prev1;
prev1 = best;
}
prev1
}-- A left fold carrying the two previous answers. The recurrence is the step function.
solve :: [Int] -> Int
solve = snd . foldl step (0, 0)
where
step (prev2, prev1) value = (prev1, max prev1 (prev2 + value))Variants to try
- The positions are arranged in a circle, so the first and last are adjacent: run the scan twice, once excluding the first position and once excluding the last, and take the larger.
- No two chosen positions within k of each other: the recurrence reaches back k + 1 instead of 2.
- Negative values allowed: the "choose nothing" floor matters, and the recurrence needs a max with 0.
- Return the chosen positions, not just the sum: keep the table after all, and walk it backwards.
Next problems
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan you reach the last position?
nums[i] is the furthest jump from position i. Can you get from the first position to the last? A reachability DP that collapses to one variable.
Open the problem → Medium20 minWays to decode a string of digits
Letters are encoded as 1 to 26. Count the ways to read a string of digits back as letters: one digit or two at a time, with zeros as the trap.
Open the problem →Write a solution and run it against the real test table.
Keep going
The cheapest way up a staircase
Each step has a cost; climb one or two steps at a time; start on step 0 or 1. Return the cheapest way past the top.
Open the problem → Medium15 minCan you reach the last position?
nums[i] is the furthest jump from position i. Can you get from the first position to the last? A reachability DP that collapses to one variable.
Open the problem → Medium20 minWays to decode a string of digits
Letters are encoded as 1 to 26. Count the ways to read a string of digits back as letters: one digit or two at a time, with zeros as the trap.
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.