What Is Kadane's Algorithm?

Kadane's algorithm keeps two running values while scanning the array once. The first is the best sum of a subarray that ends at the current position, and the second is the best sum seen anywhere so far. At each element you have a choice: extend the subarray that ended just before, or start a fresh subarray here. You take whichever is larger.

def max_subarray(nums):
    best = current = nums[0]
    for value in nums[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))

The outputs are 6 and minus one. In the first array the best contiguous run is 4, minus one, 2, 1, which sums to six, and the algorithm finds it without ever keeping more than one candidate. In the second array every value is negative, so the best subarray is the single largest element, minus one.

The mechanism is the recurrence: the best sum ending at position i is the larger of the value at i on its own and the best sum ending at i minus one plus the value at i. That is the whole algorithm, and it works because every subarray either starts at i or extends one that ended at i minus one, so those two cases cover everything. The global best is then the maximum over all the ending positions, and the scan is a single pass of O of n time and O of 1 space.

The trade-off to name is that Kadane's is a greedy-style DP that only works for the contiguous version of the problem. If the interviewer means the non-contiguous variant, where you may skip elements, the recurrence changes and a running best-single-value plus running best-sum algorithm is needed instead. Mentioning that distinction shows you understand which problem you are solving.

It returns the largest single element, which is the least negative value, because the best contiguous subarray of an all-negative array is the one with the fewest elements. The algorithm gets this for free from the recurrence, since extending a running total that is already negative can only make the result worse, so the comparison always prefers starting fresh.

def max_subarray(nums):
    best = current = nums[0]
    for value in nums[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(max_subarray([-5, -2, -9]))
print(max_subarray([0, 0, 0]))

The outputs are minus five and zero. For the first array the best answer is minus two, the single largest element, and not minus fifteen or any longer run. For the all-zero array the answer is zero, which is a useful boundary case to mention because it proves the algorithm does not confuse an empty result with a zero result.

The reason this is worth pointing out in an interview is that many people remember Kadane's algorithm incorrectly as the version that returns zero for negative input. That version silently produces an empty subarray, which is wrong for the usual formulation where at least one element must be chosen. The fix is to initialise both running values from the first element rather than from zero, which is exactly what the code does.

The trade-off to name is that if the problem statement genuinely allows the empty subarray, then returning zero for all-negative input is correct, and the initialisation should change to zero. So the honest interview answer covers both conventions: initialise from the first element for the non-empty version, initialise from zero for the empty-allowed version, and say which one you picked and why.

Track the start index of the current candidate alongside the running sum. Whenever the recurrence decides to start a fresh subarray at the current position, reset the start index too. Whenever the global best improves, record the start and the current position.

def max_subarray_range(nums):
    best_sum = current_sum = nums[0]
    best_start = best_end = current_start = 0
    for i in range(1, len(nums)):
        if current_sum + nums[i] < nums[i]:
            current_sum = nums[i]
            current_start = i
        else:
            current_sum += nums[i]
        if current_sum > best_sum:
            best_sum = current_sum
            best_start = current_start
            best_end = i
    return best_sum, best_start, best_end

print(max_subarray_range([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray_range([-5, -2, -9]))

The outputs are 6 with the range three to six, and minus five with the range zero to zero. The first range covers 4, minus one, 2, 1, which sums to six. The second shows the all-negative case: the answer is the single first element, because starting fresh at a more negative element never wins.

The extra bookkeeping is two integers and one extra comparison per element, so the algorithm stays O of n time and O of 1 space. The key insight is that the reset of the start index must happen exactly where the sum is reset, otherwise the reported range can point at a subarray whose sum does not match the reported value, which is the classic bug in this extension.

The trade-off to name is what you return when several maximum subarrays tie. This version keeps the first one it finds, because the comparison is strictly greater. If the interviewer wants the last, or the shortest, or all of them, that is a different tie-breaking rule and you should say which you chose rather than leave it implied.