Katkat
Back

Maximum Sum of Non-Adjacent Values in a Row

Walmart LabsSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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. 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

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

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

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

Input: values = []
Output: 0

There are no slots to choose.