Advance Kadane State

Practice Exercise Interview Easy Kadane's Algorithm

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement kadane_ending_states(values). Return a list where result[i] is the largest sum of any non-empty contiguous segment ending exactly at i. Return an empty list for empty input.

Starter code

def kadane_ending_states(values):
    pass

Test cases

restart-and-extend

{
  "args": [
    [
      -2,
      3,
      -1,
      4,
      -6,
      2
    ]
  ]
}

Expected: [-2,3,2,6,0,2]

all-negative

{
  "args": [
    [
      -4,
      -2,
      -7
    ]
  ]
}

Expected: [-4,-2,-7]

Wizard outline

Step 1: Handle the empty state sequence
Return [] when no nonempty segment can end at an index. Kadane ending states are defined only for existing indices.
Step 2: Seed the first ending state
Use values[0] as the best nonempty segment ending at index 0. At the first index, the only nonempty segment ending there contains the first value itself.
Step 3: Choose restart or extend
Append max(value, states[-1] + value) for each later index. Every nonempty segment ending now either starts at the current value or extends the best segment ending immediately before it.

Footguns and prerequisites

Initializing current to zero incorrectly allows an empty segment when all values are negative.
Returning the global maximum loses the requested state at every individual position.
dynamic programming

Reviewed references

Python More on Lists

Prepared Interview Problems

Maximum Contiguous Subarray Sum(opens in a new tab)
Advance Kadane State isolates current equals the optimal non-empty sum ending at the current index, not the best sum anywhere in the processed prefix. That focused state discipline is required when implementing maximum subarray as a complete Interview Problem.

Recommended approach and implementation

A best contiguous segment ending here either starts here or extends the best segment ending immediately before here. current equals the optimal non-empty sum ending at the current index, not the best sum anywhere in the processed prefix.

Why it works: For each index, the optimal non-empty segment ending there either starts at the current value or extends the optimal segment ending at the previous index. Appending the larger of those two sums therefore records the required endpoint-specific state at every index.

def kadane_ending_states(values):
    if not values:
        return []
    states = [values[0]]
    for value in values[1:]:
        states.append(max(value, states[-1] + value))
    return states