409. No Two Adjacent, In a Circle
Houses stand in a CIRCLE, so the last is next to the first. Each holds some amount, and you may not take from two neighbours. Print the largest total.
Problem #451 is the same question in a row, where the recurrence is:
best(i) = max( best(i-1), best(i-2) + value(i) )
Closing the circle breaks that, because the choice at the first house now constrains the last, and a left-to-right sweep has forgotten the first by the time it reaches the last.
Adding a flag for "did I take the first one" works and doubles the state.
There is a shorter argument. The first and last houses cannot BOTH be taken. So every valid selection avoids at least one of them, which means it is a valid selection for one of two ROWS:
houses 0 .. n-2 the first is allowed, the last is excluded
houses 1 .. n-1 the last is allowed, the first is excluded
Run the linear solution on each and take the larger. Every circular selection appears in at least one of the two, and neither row can produce a selection invalid in the circle, so the maximum is exactly right.
n = 1 needs care: the two rows are both empty and the answer is the single
house, so it is handled on its own.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ amount ≤ 10000`
Input
The first line contains an integer n.
The second line contains n space-separated non-negative amounts.
Output
Print the largest total obtainable without taking from two neighbouring houses in the circle.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.