Algorithm1 Practice1 Interview

Kadane's Algorithm

GuideCode Labs

Track the best subarray ending at each position to obtain a linear-time maximum subarray sum. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Kadane's Algorithm when the prompt's constraints and required operations match this shape: Track the best subarray ending at each position to obtain a linear-time maximum subarray sum.

On this page · Choose Extend or Restart

Checking your account…

Choose Extend or Restart

For each position, the best subarray ending there either extends the previous ending subarray or restarts at the current value. No other contiguous candidate can end at that index.

Track Ending Here and Best So Far

Ending-here answers a constrained state; best-so-far summarizes all endings processed. Update ending first, then compare it with the global best.

Trace Kadane States

Reference

def kadane_trace(values):
    ending=best=values[0];trace=[[ending,best]]
    for value in values[1:]:ending=max(value,ending+value);best=max(best,ending);trace.append([ending,best])
    return trace

Practice

Implement kadane_trace(values). Return [ending_here,best_so_far] after each value; values is nonempty.

def kadane_trace(values):
    pass

Public tests

Choose extend or restart

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Handle All Negative Arrays

Initialize from the first value rather than zero unless the empty subarray is explicitly allowed. Zero initialization incorrectly reports an empty result for all-negative input.

Recover Maximum Subarray Boundaries

Reference

def max_subarray_range(values):
    best_sum=ending=values[0];best_left=best_right=start=0
    for index in range(1,len(values)):
        if ending+values[index]<values[index]:ending=values[index];start=index
        else:ending+=values[index]
        if ending>best_sum:best_sum=ending;best_left=start;best_right=index
    return [best_sum,best_left,best_right]

Practice

Implement max_subarray_range(values). Return [sum,left,right] with inclusive bounds, preferring the earliest range on ties.

def max_subarray_range(values):
    pass

Public tests

Track restart boundaries

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Recover Subarray Boundaries

When restart wins, set the candidate left boundary to the current index. When ending becomes the strict global best, copy both boundaries. Define tie policy before choosing strict or non-strict comparisons.

Explain It in an Interview

Say: “The best subarray ending here must either be the current item alone or the prior ending plus it. I keep the better and update the best over all endings.” State O(n) time, O(1) space, empty policy, and tie behavior.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Kadane's Algorithm proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Kadane's Algorithm complete workflow	`O(n)`	`O(n)`	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.

Space

O(n) for the returned states for the focused Advance Kadane State implementation.

Assumptions

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.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Kadane's Algorithm invariant before coding and preserve it after every update, traversal step, or recursive return.
Every stored state equals the answer for its documented subproblem.
A transition reads only valid predecessor states and includes every legal choice.
A best contiguous segment ending here either starts here or extends the best segment ending immediately before here. Preserve this claim after every transition.
current equals the optimal non-empty sum ending at the current index, not the best sum anywhere in the processed prefix. Preserve this claim after every transition.

When To Use Or Avoid Kadane's Algorithm

Use It When

Use Kadane's Algorithm when this precondition is stated or can be proved: The problem has reusable subproblems and a state definition whose dependencies are acyclic or memoizable.
Use it when this maintained state removes repeated work: Every stored state equals the answer for its documented subproblem.

Choose Another Tool When

Avoid Kadane's Algorithm when this precondition is absent: The problem has reusable subproblems and a state definition whose dependencies are acyclic or memoizable.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The problem has reusable subproblems and a state definition whose dependencies are acyclic or memoizable.

Avoid

def kadane_ending_states(values):
    pass

Use instead

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

Where you will hit this: Advance Kadane State(opens in a new tab)

Breaking the state transition

Allows an empty zero-sum segment, producing zero instead of the required non-empty state on negative inputs.

Prevent it: Preserve this proof obligation: The recurrence covers every legal final choice, and the evaluation order makes each dependency available before use.

Avoid

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

Use instead

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

Where you will hit this: Advance Kadane State(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(n).

Avoid

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

Use instead

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

Where you will hit this: Maximum Contiguous Subarray Sum(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…