 | ||
In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.
Contents
The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie Mellon University (Bentley 1984).
Kadane's algorithm
Kadane's algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position
The algorithm can also be easily modified to keep track of the starting and ending indices of the maximum subarray (when max_so_far changes) as well as the case where we want to allow zero-length subarrays (with implicit sum 0) if all elements are negative.
Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple/trivial example of dynamic programming.
The runtime complexity of Kadane's algorithm is
Generalizations
Similar problems may be posed for higher-dimensional arrays, but their solutions are more complicated; see, e.g., Takaoka (2002). Brodal & Jørgensen (2007) showed how to find the k largest subarray sums in a one-dimensional array, in the optimal time bound
The Maximum sum k-disjoint subarrays can also be computed in the optimal time bound