Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Maximum subarray problem
Problem in computer science

In computer science, the maximum sum subarray problem involves finding a contiguous subarray within a one-dimensional array that has the largest sum. The problem can be solved in linear O(n) time and constant O(1) space. Formally, it requires identifying indices i and j with 1 ≤ i ≤ j ≤ n so the sum of elements from A[i] to A[j] is maximized. The array elements may be positive, negative, or zero, and by some definitions, the empty subarray sum—defined as zero in the empty sum—is allowable. A common efficient solution is Kadane's algorithm, which performs a single pass. For example, in the array [–2, 1, –3, 4, –1, 2, 1, –5, 4], the maximum sum subarray is [4, –1, 2, 1] with sum 6.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Maximum subarray problem yet.
We don't have any PDF documents related to Maximum subarray problem yet.
We don't have any Books related to Maximum subarray problem yet.
We don't have any archived web articles related to Maximum subarray problem yet.

History

The maximum subarray problem was proposed by Ulf Grenander in 1977 as a simplified model for maximum likelihood estimation of patterns in digitized images.5

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(n6) 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(n2) time using prefix sum6, improving the brute force running time of O(n3). When Michael Shamos heard about the problem, he overnight devised an O(n log n) divide-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(n)-time algorithm,789 which is as fast as possible.10 In 1982, David Gries obtained the same O(n)-time algorithm by applying Dijkstra's "standard strategy";11 in 1989, Richard Bird derived it by purely algebraic manipulation of the brute-force algorithm using the Bird–Meertens formalism.12

Grenander's two-dimensional generalization can be solved in O(n3) 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 Tamaki & Tokuyama (1998) and by Takaoka (2002). There is some evidence that no significantly faster algorithm exists; an algorithm that solves the two-dimensional maximum subarray problem in O(n3−ε) time, for any ε>0, would imply a similarly fast algorithm for the all-pairs shortest paths problem.13

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 that have unusual properties, by assigning scores to points within the sequence that are positive when a motif to be recognized is present, and negative when it is not, and then seeking the maximum subarray among these scores. These problems include conserved segments, GC-rich regions, tandem repeats, low-complexity filter, DNA binding domains, and regions of high charge.14

In computer vision, bitmap images generally consist only of positive values, for which the maximum subarray problem is trivial: the result is always the whole array. However, after subtracting a threshold value (such as the average pixel value) from each pixel, so that above-average pixels will be positive and below-average pixels will be negative, the maximum subarray problem can be applied to the modified image to detect bright areas within it.15

Kadane's algorithm

No empty subarrays admitted

Kadane's algorithm scans the given array A [ 1 … n ] {\displaystyle A[1\ldots n]} from left to right. In the j {\displaystyle j} th step, it computes the subarray with the largest sum ending at j {\displaystyle j} ; this sum is maintained in variable current_sum.16 Moreover, it computes the subarray with the largest sum anywhere in A [ 1 … j ] {\displaystyle A[1\ldots j]} , maintained in variable best_sum,17 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 j {\displaystyle j} th step, the old value of current_sum holds the maximum over all i ∈ { 1 , … , j − 1 } {\displaystyle i\in \{1,\ldots ,j-1\}} of the sum A [ i ] + ⋯ + A [ j − 1 ] {\displaystyle A[i]+\cdots +A[j-1]} . Therefore, current_sum + A [ j ] {\displaystyle +A[j]} 18 is the maximum over all i ∈ { 1 , … , j − 1 } {\displaystyle i\in \{1,\ldots ,j-1\}} of the sum A [ i ] + ⋯ + A [ j ] {\displaystyle A[i]+\cdots +A[j]} . To extend the latter maximum to cover also the case i = j {\displaystyle i=j} , it is sufficient to consider also the singleton subarray A [ j … j ] {\displaystyle A[j\;\ldots \;j]} . This is done in line 6 by assigning max ( A [ j ] , {\displaystyle \max(A[j],} current_sum + A [ j ] ) {\displaystyle +A[j])} as the new value of current_sum, which after that holds the maximum over all i ∈ { 1 , … , j } {\displaystyle i\in \{1,\ldots ,j\}} of the sum A [ i ] + ⋯ + A [ j ] {\displaystyle A[i]+\cdots +A[j]} .

Thus, the problem can be solved with the following code,19 expressed in Python.

def max_subarray(numbers): """Find the largest sum of any contiguous subarray.""" best_sum = float('-inf') current_sum = 0 for x in numbers: current_sum = max(x, current_sum + x) best_sum = max(best_sum, current_sum) return best_sum

If the input contains no positive element, the returned value is that of the largest element (i.e., the value closest to 0), or negative infinity if the input was empty. For correctness, an exception should be raised when the input array is empty, since an empty array has no maximum nonempty subarray. If the array is nonempty, its first element could be used in place of negative infinity, if needed to avoid mixing numeric and non-numeric values.

The algorithm can be adapted to the case which allows empty subarrays or to keep track of the starting and ending indices of the maximum subarray.

This algorithm calculates the maximum subarray ending at each position from the maximum subarray ending at the previous position, so it can be viewed as a case of dynamic programming.

Empty subarrays admitted

Example run

Kadane's algorithm, as originally published, is for solving the problem variant which allows empty subarrays.2021 In such variant, the answer is 0 when the input contains no positive elements (including when the input is empty). The variant is obtained with two changes in code: in line 3, best_sum should be initialized to 0 to account for the empty subarray A [ 0 … − 1 ] {\displaystyle A[0\ldots -1]}

best_sum = 0;

and line 6 in the for loop current_sum should be updated to max(0, current_sum + x).22

current_sum = max(0, current_sum + x)

As a loop invariant, in the j {\displaystyle j} th step, the old value of current_sum holds the maximum over all i ∈ { 1 , … , j } {\displaystyle i\in \{1,\ldots ,j\}} of the sum A [ i ] + ⋯ + A [ j − 1 ] {\displaystyle A[i]+\cdots +A[j-1]} .23 Therefore, current_sum + A [ j ] {\displaystyle +A[j]} is the maximum over all i ∈ { 1 , … , j } {\displaystyle i\in \{1,\ldots ,j\}} of the sum A [ i ] + ⋯ + A [ j ] {\displaystyle A[i]+\cdots +A[j]} . To extend the latter maximum to cover also the case i = j + 1 {\displaystyle i=j+1} , it is sufficient to consider also the empty subarray A [ j + 1 … j ] {\displaystyle A[j+1\;\ldots \;j]} . This is done in line 6 by assigning max ( 0 , {\displaystyle \max(0,} current_sum + A [ j ] ) {\displaystyle +A[j])} as the new value of current_sum, which after that holds the maximum over all i ∈ { 1 , … , j + 1 } {\displaystyle i\in \{1,\ldots ,j+1\}} of the sum A [ i ] + ⋯ + A [ j ] {\displaystyle A[i]+\cdots +A[j]} . Machine-verified C / Frama-C code of both variants can be found here.

Computing the best subarray's position

The algorithm can be modified to keep track of the starting and ending indices of the maximum subarray as well.

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.

Complexity

The runtime complexity of Kadane's algorithm is O ( n ) {\displaystyle O(n)} and its space complexity is O ( 1 ) {\displaystyle O(1)} .2425

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 O ( n + k ) {\displaystyle O(n+k)} .

The Maximum sum k-disjoint subarrays can also be computed in the optimal time bound O ( n + k ) {\displaystyle O(n+k)} .26

See also

Notes

Notes

References

  1. Bentley 1989, p. 69. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  2. Bentley 1989, p. 70. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  3. Bentley 1989, p. 73. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  4. Bentley 1989, p. 74. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  5. Bentley 1984, p. 868-869. - Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", Communications of the ACM, 27 (9): 865–873, doi:10.1145/358234.381162, S2CID 207565329 https://doi.org/10.1145%2F358234.381162 ↩

  6. By using a precomputed table of cumulative sums S [ k ] = ∑ x = 1 k A [ x ] {\displaystyle S[k]=\sum _{x=1}^{k}A[x]} to compute the subarray sum ∑ x = i j A [ x ] = S [ j ] − S [ i − 1 ] {\displaystyle \sum _{x=i}^{j}A[x]=S[j]-S[i-1]} in constant time ↩

  7. Bentley 1984, p. 868-869. - Bentley, Jon (1984), "Programming Pearls: Algorithm Design Techniques", Communications of the ACM, 27 (9): 865–873, doi:10.1145/358234.381162, S2CID 207565329 https://doi.org/10.1145%2F358234.381162 ↩

  8. Bentley 1989, p. 76-77. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  9. Gries 1982, p. 211. - Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF), Science of Computer Programming, 2 (3): 207–241, doi:10.1016/0167-6423(83)90015-1, hdl:1813/6370 https://core.ac.uk/download/pdf/82596333.pdf ↩

  10. since every algorithm must at least scan the array once which already takes O(n) time ↩

  11. Gries 1982, p. 209-211. - Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF), Science of Computer Programming, 2 (3): 207–241, doi:10.1016/0167-6423(83)90015-1, hdl:1813/6370 https://core.ac.uk/download/pdf/82596333.pdf ↩

  12. Bird 1989, Sect.8, p.126. - Bird, Richard S. (1989), "Algebraic Identities for Program Calculation", The Computer Journal, 32 (2): 122–126, doi:10.1093/comjnl/32.2.122 https://doi.org/10.1093%2Fcomjnl%2F32.2.122 ↩

  13. Backurs, Dikkala & Tzamos 2016. - Backurs, Arturs; Dikkala, Nishanth; Tzamos, Christos (2016), "Tight Hardness Results for Maximum Weight Rectangles", Proc. 43rd International Colloquium on Automata, Languages, and Programming: 81:1–81:13, doi:10.4230/LIPIcs.ICALP.2016.81, S2CID 12720136 https://doi.org/10.4230%2FLIPIcs.ICALP.2016.81 ↩

  14. Ruzzo & Tompa (1999); Alves, Cáceres & Song (2004) - Ruzzo, Walter L.; Tompa, Martin (1999), "A Linear Time Algorithm for Finding All Maximal Scoring Subsequences", in Lengauer, Thomas; Schneider, Reinhard; Bork, Peer; Brutlag, Douglas L.; Glasgow, Janice I.; Mewes, Hans-Werner; Zimmer, Ralf (eds.), Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, August 6–10, 1999, Heidelberg, Germany, AAAI, pp. 234–241 https://www.aaai.org/Library/ISMB/1999/ismb99-027.php ↩

  15. Bae & Takaoka (2006); Weddell et al. (2013) - Bae, Sung Eun; Takaoka, Tadao (2006), "Improved Algorithms for the \emph{K}-Maximum Subarray Problem", The Computer Journal, 49 (3): 358–374, doi:10.1093/COMJNL/BXL007 https://doi.org/10.1093%2FCOMJNL%2FBXL007 ↩

  16. named MaxEndingHere in Bentley (1989), and c in Gries (1982) - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  17. named MaxSoFar in Bentley (1989), and s in Gries (1982) - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  18. In the Python code below, A [ j ] {\displaystyle A[j]} is expressed as x, with the index j {\displaystyle j} left implicit. ↩

  19. Bentley 1989, p. 78,171. Bentley, like Gries, first introduces the variant admitting empty subarrays, see below, and describes only the changes. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  20. Bentley 1989, p. 74. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  21. Gries 1982, p. 211. - Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF), Science of Computer Programming, 2 (3): 207–241, doi:10.1016/0167-6423(83)90015-1, hdl:1813/6370 https://core.ac.uk/download/pdf/82596333.pdf ↩

  22. While Bentley (1989) does not mention this difference, using x instead of 0 in the above version without empty subarrays achieves maintaining its loop invariant current_sum = max i ∈ { 1 , . . . , j − 1 } A [ i ] + . . . + A [ j − 1 ] {\displaystyle =\max _{i\in \{1,...,j-1\}}A[i]+...+A[j-1]} at the beginning of the j {\displaystyle j} th step. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  23. This sum is 0 {\displaystyle 0} when i = j {\displaystyle i=j} , corresponding to the empty subarray A [ j … j − 1 ] {\displaystyle A[j\ldots j-1]} . ↩

  24. Bentley 1989, p. 74. - Bentley, Jon (May 1989), Programming Pearls (2nd? ed.), Reading, MA: Addison Wesley, ISBN 0-201-10331-1 https://archive.org/details/programmingpearl00bent ↩

  25. Gries 1982, p. 211. - Gries, David (1982), "A Note on the Standard Strategy for Developing Loop Invariants and Loops" (PDF), Science of Computer Programming, 2 (3): 207–241, doi:10.1016/0167-6423(83)90015-1, hdl:1813/6370 https://core.ac.uk/download/pdf/82596333.pdf ↩

  26. Bengtsson & Chen 2007. - Bengtsson, Fredrik; Chen, Jingsen (2007), Computing maximum-scoring segments optimally (PDF) (Research report), Luleå University of Technology http://ltu.diva-portal.org/smash/get/diva2:995901/FULLTEXT01.pdf ↩