Kadane Algorithm
Kadane's algorithm solves the maximum subarray problem: given an array of integers that may include negative values, find the contiguous subarray with the ...
Finding the Maximum Subarray Sum in Linear Time
Kadane's algorithm solves the maximum subarray problem: given an array of integers that may include negative values, find the contiguous subarray with the largest sum. The algorithm runs in O(n) time and O(1) space, making it one of the most elegant examples of dynamic programming thinking in action.
The key insight is this: as you scan the array from left to right, at each position you make a local decision. Either you extend the current subarray by adding the current element, or you start a fresh subarray beginning at the current element. You extend if the running sum remains positive; you restart if it drops to or below zero, because a negative running sum can only hurt future subarrays.
The algorithm maintains two variables: current_max, the sum of the best subarray ending at the current position, and global_max, the largest sum seen so far across all positions. Initialize both to the first element. Then for each subsequent element e, set current_max to the maximum of e alone and current_max plus e. Update global_max to the maximum of global_max and current_max.
In pseudocode: current_max = A[0], global_max = A[0], then for i from 1 to n-1: current_max = max(A[i], current_max + A[i]), global_max = max(global_max, current_max). When the loop ends, global_max holds the answer.
If all elements are negative, the algorithm correctly returns the largest (least negative) single element, because each position considers starting fresh with just that element. This handles the edge case that simpler implementations miss.
To also track the indices of the maximum subarray, maintain start, end, and temp_start variables. When you restart a new subarray, update temp_start to the current index. When global_max is updated, set start to temp_start and end to the current index.
Kadane's algorithm is a one-dimensional dynamic programming solution where the recurrence is: dp[i] equals max(A[i], dp[i minus one] plus A[i]). Because dp[i] only depends on dp[i minus one], you do not need to store the entire dp array, just the previous value, giving O(1) space.
Worked example: array is [-2, 1, -3, 4, -1, 2, 1, -5, 4]. Tracing the algorithm: current_max after each step is -2, 1, -2, 4, 3, 5, 6, 1, 5. global_max peaks at 6, corresponding to the subarray [4, -1, 2, 1].
Interview tip: Kadane's algorithm is a must-know. If the interviewer asks for the subarray indices, remember to track temp_start and update start when global_max is updated.