DSA interview question

Maximum Sum of Non-Adjacent Elements

Medium · Algorithms · Topics: dynamic programming, house robber

The problem

You're building a resource-allocation optimizer for a construction company. There's a row of n plots of land along a highway, each with an estimated profit if developed. Due to zoning regulations, you cannot develop two adjacent plots (to maintain required setback distances between construction sites). Your task: given the profit values for each plot, find the maximum total profit achievable by selecting a subset of plots such that no two selected plots are adjacent.

Example: profits [2, 1, 4, 9] → select plots 0 and 2, or plot 1 and 3, but selecting plot 2 and 3 alone (9+... no, they're adjacent) — best is 2 + 9 = 11 (plots 0 and 3 are not optimal either; verify: 1+9=10, 2+9=11, 2+4=6) → answer is 11.

Function signature

int maximumNonAdjacentSum(vector<int>& nums);

Test cases

Input `nums`	Output	Explanation
`[2,1,4,9]`	11	Select plots 0 and 3 → 2+9=11
`[1,2,4]`	5	Select plots 0 and 2 → 1+4=5
`[]`	0	No plots, nothing to select
`[5]`	5	Single plot, select it
`[3,7]`	7	Two plots, select the bigger one
`[5,5,10,100,10,5]`	110	Select plots 0/1 (5), plot 3 (100), plot 5 (5) → best combo = 5+100+5=110
`[1,2,3,1,5]`	9	Select plots 0,2,4 → 1+3+5=9

(Confirm: all values are positive per problem statement, so this differs slightly from House Robber where 0/negative edge cases might need explicit handling — here selecting nothing is never beneficial.)

How interviewers phrase it

"Given an array of positive numbers, select a subset such that no two chosen elements are adjacent in the array, maximizing the sum."
This is functionally identical to House Robber (LeetCode 198) — same recurrence, different theming. Interviewers sometimes present this first (as the "pure DP" version) before wrapping it in the House Robber story, or vice versa.
Watch for interviewers testing whether you recognize the pattern even when the story/constraints are phrased slightly differently (e.g., "positive numbers" vs "house robber" framing).

Clarifying questions to ask

Are all elements guaranteed positive, as stated? (This matters: with positive-only values, you'd never intentionally pick fewer elements than optimal, unlike if negatives were allowed.)
Can the array be empty? What should be returned in that case — 0?
Does "non-adjacent" strictly mean not consecutive by index, or could there be a different adjacency definition (e.g., circular array)?
Do you need just the maximum sum, or also the actual subset of indices/elements chosen?
Is there any constraint on array size that would push toward an O(1) space solution over O(n)?

Follow-ups to expect

"This is the same as House Robber — can you prove/explain why?"
"Can you solve this with O(1) space?"
"What if the array were circular (first and last elements considered adjacent)?"
"What if negative numbers were allowed?"
"Can you return the actual subset of chosen elements?"
"What if you needed the maximum sum choosing exactly k non-adjacent elements (not just any number)?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview