Definition
- Binary decision – at each index, either skip (keep dp[i-1]) or take (add value to dp[i-2]).
- Recurrence –
dp[i] = max(dp[i-1], dp[i-2] + values[i]). - Rolling variables – only dp[i-1] and dp[i-2] are needed, so
oneBackandtwoBackgive O(1) space. - Circular variant – first and last are also adjacent: run twice, excluding first then excluding last, take the max.
- Complexity – O(n) time, O(1) space.
National Bank of India runs a promotional cash-back on consecutive days, but a fraud rule forbids claiming cash-back on two back-to-back days. Rajesh picks the days that maximize his total cash-back without choosing two in a row.
Understanding the Concepts
What is the problem?
Given an array of non-negative values, select a subset with the maximum total such that no two selected elements are adjacent in the array. This is the classic House Robber problem.
How does the recurrence work?
- At each index i, you face a binary choice:
- Skip: the best total is whatever it was at index i-1.
- Take: add the current value to the best total from index i-2 (the previous element is forbidden).
The answer at each position is max(skip, take).
package com.bank.service;
public class CashBackOptimizer {
public static long maxNonAdjacent(int[] values) {
if (values == null || values.length == 0) return 0;
if (values.length == 1) return values[0];
long twoBack = 0;
long oneBack = 0;
for (int v : values) {
long take = twoBack + v;
long best = Math.max(oneBack, take);
twoBack = oneBack;
oneBack = best;
}
return oneBack;
}
public static void main(String[] args) {
// Daily cash-back amounts at National Bank of India
int[] cashBack = {2, 7, 9, 3, 1};
System.out.println("Max cash-back: " + maxNonAdjacent(cashBack));
}
}
Max cash-back: 12
The best selection is indices 0, 2, 4 (values 2, 9, 1) for a total of 12.
How do the rolling variables work?
values: [2, 7, 9, 3, 1]
i=0: take=0+2=2, best=max(0,2)=2 twoBack=0, oneBack=2
i=1: take=0+7=7, best=max(2,7)=7 twoBack=2, oneBack=7
i=2: take=2+9=11, best=max(7,11)=11 twoBack=7, oneBack=11
i=3: take=7+3=10, best=max(11,10)=11 twoBack=11, oneBack=11
i=4: take=11+1=12, best=max(11,12)=12 twoBack=11, oneBack=12
Answer: 12
How do you handle the circular variant?
- When the array is circular (first and last elements are also adjacent), run the linear scan twice:
- Once on elements 0 to n-2 (exclude last).
- Once on elements 1 to n-1 (exclude first).
Take the maximum of the two results.
public static long maxNonAdjacentCircular(int[] values) {
if (values.length == 1) return values[0];
return Math.max(
maxNonAdjacentRange(values, 0, values.length - 2),
maxNonAdjacentRange(values, 1, values.length - 1)
);
}
private static long maxNonAdjacentRange(int[] values, int start, int end) {
long twoBack = 0, oneBack = 0;
for (int i = start; i <= end; i++) {
long take = twoBack + values[i];
long best = Math.max(oneBack, take);
twoBack = oneBack;
oneBack = best;
}
return oneBack;
}
What are edge cases?
- Empty array: return 0.
- Single element: return that element.
- Two elements: return the larger.
- All equal values: pick every other element.
What are common mistakes?
// Wrong: using dp[i-1] for take instead of dp[i-2]
long take = oneBack + v; // WRONG: oneBack is dp[i-1], adjacent!
// Correct: use twoBack for take
long take = twoBack + v; // twoBack is dp[i-2], not adjacent
How is this different from standard Kadane?
| Feature | House Robber | Kadane (max subarray) |
|---|---|---|
| Constraint | no two adjacent | contiguous subarray |
| Decision | skip or take | extend or restart |
| Dependencies | dp[i-1] and dp[i-2] | dp[i-1] only |
| Typical use | non-adjacent selection | best contiguous sum |
What should a senior engineer know?
The two-variable rolling approach is a textbook example of space optimization in DP. The same pattern applies to staircase problems, tiling problems, and any recurrence that only looks a fixed number of steps back. For monetary values, use long or BigDecimal to handle large cumulative totals.
What are common interview follow-up questions?
- How would you return which elements were selected, not just the total?
- What if you can skip at most two consecutive elements instead of just one?
- What if the values can be negative?
Visual Overview
values: [2, 7, 9, 3, 1] Decision at each position: i=0: take 2 best=2 i=1: skip(2) vs take(0+7=7) best=7 i=2: skip(7) vs take(2+9=11) best=11 i=3: skip(11) vs take(7+3=10) best=11 i=4: skip(11) vs take(11+1=12) best=12 Selected: [2, 9, 1] → total 12
Key Takeaway
House Robber is the canonical maximum non-adjacent sum problem. At every position you face a binary decision: skip the current value and keep the previous best, or take the current value and add it to the best from two positions back. The answer at each position is the larger of the two options.
Since every decision looks only one and two positions behind, two rolling variables replace the entire DP table, giving linear time and constant space. This contrasts with the exponential cost of trying every subset.
The circular variant, where the first and last elements are also adjacent, is solved by running the linear scan twice: once excluding the first element and once excluding the last, taking the better result.
In a banking project at National Bank of India, a cash-back promotion forbade claiming on two consecutive days. The analytics team wanted the maximum total a customer could legitimately claim. The linear scan over daily values produced the answer, and the circular variant handled wrap-around promotions.
Remember one sentence: at each element, choose the better of skipping it or taking it plus the best from two back.
---