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.
A row of `n` slots holds non-negative integer values: `values[i]` is the value of slot `i`, for `0 <= i < n`. 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), and return the largest possible sum of the values in the chosen slots.
Implement `max_non_adjacent_sum(values)`, which returns that maximum sum as an integer.
**Rules**
- A selection is valid when it never contains two consecutive indices.
- The row does not wrap around: slot `n - 1` and slot `0` are not neighbors through the ends of the row. Only indices `i` and `i + 1` are adjacent.
- Choosing no slot at all is allowed, so the answer is never negative. An empty row returns `0`.
- Return only the maximum sum, not the chosen slots. The maximum is a single number even when several selections achieve it.
**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. It fits in a 32-bit signed integer and never exceeds 2^31 - 1.
**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.
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; it fits in a 32-bit signed integer and never exceeds 2^31 - 1
Examples
Input: ([],)
Expected Output: 0
Explanation: Empty row: there are no slots to choose, so the sum is 0.
Input: ([0],)
Expected Output: 0
Explanation: Single zero slot: taking it or not gives 0.
Hints
- Choosing no slot is allowed, so the answer is never negative and an empty row gives 0.
- Only indices i and i + 1 conflict; the row does not wrap around, which is why Example 2 can take both its first and its last slot.
- Taking every other slot is not always optimal: in Example 2 both alternating selections give only 5, while the best selection gives 8.