House robber (row)

Challenge

Implement:

long long rob_linear(const int *a, int n);

Return the maximum sum of elements of a[0..n-1] (non-negative) such that no two chosen elements are adjacent.

Input format

Non-negative a, count n.

Output format

Maximum non-adjacent sum.

Constraints

O(1) extra space suffices.

Starter code

#include <stddef.h>
/* Maximum sum of non-adjacent elements of a[0..n-1] (non-negative). */
long long rob_linear(const int *a,int n){ (void)a;(void)n; return 0; }

Common mistakes

Only considering 'take every other' — the optimum can skip two in a row.

Edge cases to handle

Empty -> 0; single -> that value.

Background lessons

• House robber