Maximum Sum of Non-Adjacent Values in a Row
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A row of `n` slots holds non-negative integer values. Choose any set of slots such that no two chosen slots are adjacent: for every `i`, slots `i` and `i + 1` cannot both be chosen. Return the largest possible sum of the values in the chosen slots.
Choosing no slot at all is allowed, so the answer is never negative.
### Function Signature
```python
def max_non_adjacent_sum(values: list[int]) -> int:
```
### Rules
- `values[i]` is the value of slot `i`, for `0 <= i < n`.
- A selection is valid when it never contains two consecutive indices. The first and last slots are not adjacent to each other: the row does not wrap around.
- Return only the maximum sum, not the chosen slots. The maximum is a single number even when several selections achieve it.
- An empty row returns `0`.
### Constraints
- `0 <= n <= 100000`, where `n = len(values)`
- `0 <= values[i] <= 10000`
- At most 50,000 slots can be chosen, so the answer is at most 500,000,000, which fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: values = [2, 7, 9, 3, 1]
Output: 12
```
Choosing slots 0, 2 and 4 gives 2 + 9 + 1 = 12. Choosing slots 1 and 3 gives only 10.
**Example 2**
```text
Input: values = [4, 1, 1, 4]
Output: 8
```
Slots 0 and 3 are not adjacent, so both can be chosen for 4 + 4 = 8. Choosing slots 0 and 2, or slots 1 and 3, gives only 5.
**Example 3**
```text
Input: values = []
Output: 0
```
There are no slots to choose.
Overview: A coding problem that asks for the largest total obtainable from a row of non-negative values when no two chosen positions may be adjacent. It tests reasoning about take-or-skip choices, edge cases such as empty and single-element rows, and a solution fast enough for rows of up to 100,000 values.