House robber

Overview

The house-robber problem asks for the maximum sum of a subset of array elements with the constraint that no two chosen elements are adjacent. The insight is that at each position you have exactly two states: include this element (and therefore take the best total that excluded its neighbour) or exclude it (and keep the best total so far either way). Two running variables carry those states, so the whole problem is a single pass in O(1) space. The circular variant — where the first and last elements are also adjacent — reduces neatly to two runs of the linear version.

Why it matters

Non-adjacent selection is a real constraint shape: scheduling jobs that cannot run back to back, choosing time slots with a mandatory gap, picking non-overlapping intervals, selecting sensors that must not be neighbours. The include/exclude state pair is also the simplest example of a DP whose state is not just an index — a pattern that generalises to far harder problems.

Core concepts

Two states per position. incl is the best total that does use the current element; excl is the best that does not. At each step: new_incl = excl + a[i] (using this element requires the previous to be excluded) and new_excl = max(incl, excl) (skipping it lets you keep whichever was better).

Order matters. Compute new_incl from the old excl before overwriting anything — updating in the wrong order silently allows adjacent picks.

The answer. max(incl, excl) at the end, since the optimum may or may not use the final element.

The circular variant. If the array is a ring, the first and last elements conflict. Because at most one of them can be chosen, the answer is max(rob(0..n-2), rob(1..n-1)) — two linear runs, each excluding one endpoint.

The n == 1 special case. Both ranges of the circular reduction are empty or malformed for a single element, so return a[0] directly.

Non-negative assumption. With negative values, "take nothing" may beat any selection; decide whether the empty set is allowed and seed accordingly.

Syntax notes

/* best non-adjacent sum over a[lo..hi] inclusive */
long long rob(const int *a, int lo, int hi) {
    long long incl = 0, excl = 0;
    for (int i = lo; i <= hi; i++) {
        long long ni = excl + a[i];              /* use OLD excl */
        long long ne = (incl > excl) ? incl : excl;
        incl = ni; excl = ne;                    /* commit together */
    }
    return (incl > excl) ? incl : excl;
}

long long rob_circular(const int *a, int n) {
    if (n == 1) return a[0];                     /* both ranges degenerate */
    long long x = rob(a, 0, n - 2);              /* drop the last  */
    long long y = rob(a, 1, n - 1);              /* drop the first */
    return (x > y) ? x : y;
}

Key points:

• Compute both new values before assigning either; otherwise new_excl sees the already-updated incl.
• The circular case is two linear runs, not a new algorithm.
• long long — sums of many elements overflow int easily.

Lesson

The house robber maximizes loot from a line of houses where you can't rob two adjacent ones — a clean take-or-skip DP. The circular variant (first and last are neighbours) reduces to two linear passes: rob everything but the last house, or everything but the first.

Code examples

#include <stdio.h>
static long long rob(const int*a,int lo,int hi){long long incl=0,excl=0;for(int i=lo;i<=hi;i++){long long ni=excl+a[i];long long ne=incl>excl?incl:excl;incl=ni;excl=ne;}return incl>excl?incl:excl;}
static long long rob_circular(const int*a,int n){if(n==1)return a[0];long long x=rob(a,0,n-2),y=rob(a,1,n-1);return x>y?x:y;}
int main(void){
    int houses[]={2,7,9,3,1};
    printf("max loot, houses in a row      = %lld\n", rob(houses,0,4));
    printf("max loot, houses in a circle   = %lld\n", rob_circular(houses,5));
    return 0;
}

Line by line

Common mistakes

Assuming 'every other house' is optimal; mishandling the circular first-last adjacency.

Debugging tips

Compiler errors and warnings:

• -Wsign-compare on the loop bounds; keep indices int.
• No warning for the update-order bug — it is a logic error.

Runtime symptoms:

• The result includes adjacent elements. You assigned incl before computing excl (or used the new excl for incl). Compute both, then commit.
• Circular version wrong for n == 1. The rob(a, 0, -1) range is empty and rob(a, 1, 0) is malformed — special-case it.
• Circular version wrong for n == 2. Should return the larger element; verify the two ranges each cover exactly one element.
• Overflow on long arrays. Use long long.
• Negative values give 0. That is correct if the empty selection is allowed; if not, seed incl from the first element instead.

Technique: test {2,7,9,3,1} (linear answer 12) and the same array circular (answer 11 — you cannot take both ends).

Memory safety

• No allocation at all. The O(1)-space form has nothing to leak; that is a genuine safety benefit over a table-based version.
• Range validity. rob(a, lo, hi) reads a[lo..hi]; the circular caller must guarantee hi <= n-1 and lo >= 0. The n == 1 guard exists precisely because n-2 would be -1.
• Empty ranges. When lo > hi the loop body never runs and the function returns 0 — safe, but make sure that is the answer you want.
• Overflow. Signed overflow is undefined; long long accumulators plus a bounded input range keep the arithmetic well defined.
• Const-correctness. Taking const int *a documents that the input is not modified and lets the compiler catch accidental writes.

Real-world uses

Concrete uses: Scheduling tasks that require a cooldown between runs. Choosing advertising slots that cannot be back to back. Selecting non-adjacent sensors or cell towers to avoid interference. Picking non-overlapping time intervals for maximum value. The circular variant models schedules that wrap around a day or a ring topology.

Professional best practices:

Beginner:

• Compute both new states before committing either.
• Test the linear and circular answers on the same array; they should differ when both endpoints are attractive.

Intermediate:

• Recognise the reduction pattern: a circular constraint often becomes two linear runs with one endpoint excluded each.
• Keep the O(1) form unless you must reconstruct which elements were chosen, which needs the full table.
• State explicitly whether the empty selection is permitted — it changes the seeding for negative inputs.

Practice tasks

1. (Beginner) Linear robber. Implement long long rob(const int *a, int lo, int hi) with the include/exclude pair. Example: {2,7,9,3,1} -> 12. Concepts: two-state DP, O(1) space.

2. (Beginner) Circular robber. Implement rob_circular using two linear runs. Requirements: handle n == 1. Example: {2,3,2} -> 3. Concepts: constraint reduction.

3. (Intermediate) Report the selection. Extend the linear version to output which indices were chosen. Hint: this needs a table, not two scalars — record the decision at each step. Concepts: the space/information trade-off.

4. (Intermediate) Minimum gap of two. Generalise so chosen elements must be at least three apart. Hint: the include state now draws from two positions back. Concepts: widening the state.

Summary

Non-adjacent selection is a two-state DP: incl (best total using the current element) comes from the previous excl plus this value, while excl keeps the better of the two previous states. Compute both before committing either, or the update silently permits adjacent picks. The answer is the larger of the two at the end, and the whole thing runs in one pass with no allocation. A circular array reduces to two linear runs — one dropping the first element, one dropping the last — with n == 1 handled separately.

Practice with these exercises

• House robber (row)
• House robber (circle)