Maximum Non-Adjacent Sum

Question

Each value in `amounts` is the reward available at one location. You may select any subset, but cannot select two adjacent locations. Return the largest total reward.

```python
def max_non_adjacent_sum(amounts: list[int]) -> int: ...
```

Assume rewards are non-negative. The empty input returns `0`. Produce an `O(n)`-time solution and then reduce its auxiliary space to `O(1)`.

## Staged follow-ups

1. Return the selected indices, with deterministic tie-breaking.
2. Arrange the locations in a circle, so the first and last are also adjacent.
3. Generalize to a tree where directly connected nodes cannot both be selected.