Kadane's Algorithm with Indices

Interview Prep

Warm-upDynamic Programming Variation of Maximum Subarrayarraysdpkadane

The problem

Same as Maximum Subarray, but return the start and end indices of the optimal subarray — not just the sum. Interviewers love this follow-up because it distinguishes candidates who memorised a 4-line Kadane from those who understand the recurrence.

Pattern: track the start when you restart

The standard Kadane recurrence is current = max(nums[i], current + nums[i]). The decision boils down to "restart" vs "extend":

Two index variables, both updated alongside current: cur_lo (start of the segment currently being built) and the pair (best_lo, best_hi) (the best segment seen so far). Update best only when current beats it, and snap best_lo to whatever cur_lo is now.

Solution

def max_subarray_with_indices(nums: list[int]) -> tuple[int, int, int]:
    """Return (best_sum, lo, hi) — the indices of the optimal subarray (inclusive)."""
    best = current = nums[0]
    best_lo = best_hi = 0
    cur_lo = 0

    for i in range(1, len(nums)):
        x = nums[i]
        if x > current + x:
            current = x                # restart — start a fresh subarray at i
            cur_lo = i
        else:
            current = current + x      # extend the current subarray

        if current > best:
            best = current
            best_lo, best_hi = cur_lo, i

    return best, best_lo, best_hi

Trace

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i=0  (init):  current=-2, best=-2, best_lo=0, best_hi=0, cur_lo=0
i=1, x=1:     1 > -2+1=-1 -> restart. current=1, cur_lo=1.
              1 > -2 -> best=1, best_lo=1, best_hi=1.
i=2, x=-3:    -3 > 1-3=-2? no -> extend. current=-2.   best unchanged.
i=3, x=4:     4 > -2+4=2 -> restart. current=4, cur_lo=3.
              4 > 1 -> best=4, best_lo=3, best_hi=3.
i=4, x=-1:    -1 > 4-1=3? no -> extend. current=3.   best unchanged.
i=5, x=2:     2 > 3+2=5? no -> extend. current=5.
              5 > 4 -> best=5, best_lo=3, best_hi=5.
i=6, x=1:     extend. current=6.   best=6, best_hi=6.
i=7, x=-5:    extend. current=1.   best unchanged.
i=8, x=4:     4 > 1+4=5? no -> extend. current=5.   best unchanged.

return (6, 3, 6)   subarray [4, -1, 2, 1]

Edge case: all-negative array

A standard gotcha: if every element is negative, the optimal "subarray" is the single largest (least negative) element. The recurrence above handles this naturally because we initialize best and current from nums[0] and never let an empty subarray sneak in. 

# Edge case: all elements negative.
# nums = [-3, -1, -4]
# i=0: current=-3, best=-3, lo=hi=0, cur_lo=0
# i=1, x=-1: -1 > -3 + -1 = -4 -> restart. current=-1, cur_lo=1.
#          -1 > -3 -> best=-1, lo=1, hi=1.
# i=2, x=-4: -4 > -1 + -4 = -5? yes -> restart. current=-4, cur_lo=2.
#          -4 > -1? no -> best unchanged.
# return (-1, 1, 1)   single-element subarray [-1]  ✓

Complexity

Strict equality and ties

Using strict > when comparing nums[i] to current + nums[i] means that on ties we extend rather than restart. This biases the result toward the longest subarray achieving the optimal sum. If the spec wants the shortest, flip to ≥ in the restart condition. Worth asking the interviewer.