Find the contiguous subarray with the largest sum (Kadane's algorithm).

How to think about it

When the words “contiguous” and “maximum sum” land in the same sentence, the interviewer is listening for Kadane’s. The thing they want you to skip is the O(n²) habit of summing every (i, j) window. The insight that earns the nod is smaller and sharper: a running subarray is only worth keeping while its sum stays positive, because the moment it turns negative it can only drag down whatever comes next.

So carry one running sum and ask a single question at every element: is the subarray ending just before me worth extending, or should I throw it away and start fresh here? Extending wins when the running sum is positive; starting fresh wins when it has gone negative — and both branches collapse into current_sum = max(num, current_sum + num). After each step, compare against a separate best so the all-time maximum survives even if the run later decays. Two scalars, one forward pass.

A worked example

def max_subarray(nums):
    current_sum = nums[0]
    best = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)   # extend or restart
        best = max(best, current_sum)                # remember the high-water mark
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # subarray [4,-1,2,1]
print(max_subarray([1]))                               # single element
print(max_subarray([-3, -1, -2]))                      # all negative
print(max_subarray([1, 2, 3, 4]))                      # all positive -> total

# Trace the running sum against the global best
def max_subarray_verbose(nums):
    cur = best = nums[0]
    print(f"  i=0, num={nums[0]}: cur={cur}, best={best}")
    for i, num in enumerate(nums[1:], start=1):
        cur = max(num, cur + num)
        best = max(best, cur)
        print(f"  i={i}, num={num}: cur=max({num}, prev+{num})={cur}, best={best}")
    return best

print("Trace for [-2,1,-3,4,-1,2,1,-5,4]:")
max_subarray_verbose([-2, 1, -3, 4, -1, 2, 1, -5, 4])

6
1
-1
10
Trace for [-2,1,-3,4,-1,2,1,-5,4]:
  i=0, num=-2: cur=-2, best=-2
  i=1, num=1: cur=max(1, prev+1)=1, best=1
  i=2, num=-3: cur=max(-3, prev+-3)=-2, best=1
  i=3, num=4: cur=max(4, prev+4)=4, best=4
  i=4, num=-1: cur=max(-1, prev+-1)=3, best=4
  i=5, num=2: cur=max(2, prev+2)=5, best=5
  i=6, num=1: cur=max(1, prev+1)=6, best=6
  i=7, num=-5: cur=max(-5, prev+-5)=1, best=6
  i=8, num=4: cur=max(4, prev+4)=5, best=6

Follow cur through the trace. At i=1 the running sum restarts — the leading -2 is dead weight, so cur resets to 1 rather than -1. It climbs to 6 by i=6 as the run [4,-1,2,1] accumulates, and best latches that 6. The dip at i=7 and the trailing 4 at i=8 push cur around afterwards, but best refuses to forget the peak — which is exactly why you keep a second variable and return best, not cur.