In computer science, the maximum sum subarray problem is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A of numbers. Formally, the task is to find indices and with, such that the sum is as large as possible. Each number in the input array A could be positive, negative, or zero. For example, for the array of values , the contiguous subarray with the largest sum is , with sum 6. Some properties of this problem are:
If the array contains all non-negative numbers, then the problem is trivial; a maximum subarray is the entire array.
If the array contains all non-positive numbers, then a solution is any subarray of size 1 containing the maximal value of the array.
Several different sub-arrays may have the same maximum sum.
The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images. Grenander was looking to find a rectangular subarray with maximum sum, in a two-dimensional array of real numbers. A brute-force algorithm for the two-dimensional problem runs in O time; because this was prohibitively slow, Grenander proposed the one-dimensional problem to gain insight into its structure. Grenander derived an algorithm that solves the one-dimensional problem in O time, improving the brute force running time of O. When Michael Shamos heard about the problem, he overnight devised an Odivide-and-conquer algorithm for it. Soon after, Shamos described the one-dimensional problem and its history at a Carnegie Mellon University seminar attended by Jay Kadane, who designed within a minute an O-time algorithm, which is as fast as possible. In 1982, David Gries obtained the same O-time algorithm by applying Dijkstra's "standard strategy"; in 1989, Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using the Bird–Meertens formalism. Grenander's two-dimensional generalization can be solved in O time either by using Kadane's algorithm as a subroutine, or through a divide-and-conquer approach. Slightly faster algorithms based on distance matrix multiplication have been proposed by and by. There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximum subarray problem in O time, for any ε>0, would imply a similarly fast algorithm for the all-pairs shortest paths problem.
Applications
Maximum subarray problems arise in many fields, such as genomic sequence analysis and computer vision. Genomic sequence analysis employs maximum subarray algorithms to identify important biological segments of protein sequences. These problems include conserved segments, GC-rich regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge. In computer vision, maximum-subarray algorithms are used on bitmap images to detect the brightest area in an image.
Kadane's algorithm
algorithm scans the given array from left to right. In the th step, it computes the subarray with the largest sum ending at ; this sum is maintained in variable current_sum. Moreover, it computes the subarray with the largest sum anywhere in, maintained in variable best_sum, and easily obtained as the maximum of all values of current_sum seen so far, cf. line 7 of the algorithm. As a loop invariant, in the th step, the old value of current_sum holds the maximum over all of the sum. Therefore, current_sum is the maximum over all of the sum. To extend the latter maximum to cover also the case, it is sufficient to consider also the empty subarray. This is done in line 6 by assigning current_sum as the new value of current_sum, which after that holds the maximum over all of the sum. Thus, the problem can be solved with the following code, expressed here in Python: def max_subarray: """Find the largest sum of any contiguous subarray.""" best_sum = 0 # or: float current_sum = 0 for x in numbers: current_sum = max best_sum = max return best_sum
This version of the algorithm will return 0 if the input contains no positive elements. For the variant of the problem which disallows empty subarrays, best_sum should be initialized to negative infinity instead and also in the for loopcurrent_sum should be updated as max. In that case, if the input contains no positive element, the returned value is that of the largest element, or negative infinity if the input was empty. The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well: def max_subarray: """Find a contiguous subarray with the largest sum.""" best_sum = 0 # or: float best_start = best_end = 0 # or: None current_sum = 0 for current_end, x in enumerate: if current_sum <= 0: # Start a new sequence at the current element current_start = current_end current_sum = x else: # Extend the existing sequence with the current element current_sum += x if current_sum > best_sum: best_sum = current_sum best_start = current_start best_end = current_end + 1 # the +1 is to make 'best_end' exclusive return best_sum, best_start, best_end
In Python, arrays are indexed starting from 0, and the end index is typically excluded, so that the subarray in the array would start at index 1 and end at index 3. Because of the way this algorithm uses optimal substructures 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.,. 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
