|
==Generalizations==
Similar problems may be posed for higher dimensional arrays, but their solution is more complicated; see, e.g., {{harvtxt|Takaoka|2002}}. {{harvtxt|Brodal|Jørgensen|2007}} showed how to find the ''k'' largest subarray sums in a one-dimensional array, in the optimal time bound <math>\mathcal{O}(n + k)</math>.
==References==
*{{citation
| first = Jon | last = Bentley | authorlink = Jon Bentley
| title = Programming pearls: algorithm design techniques
| journal = [[Communications of the ACM]]
| volume = 27 | issue = 9 | year = 1984 | doi = 10.1145/358234.381162 | pages = 865–873}}.
*{{citation
| first1 = Gerth Stølting | last1 = Brodal | first2 = Allan Grønlund | last2 = Jørgensen
| contribution = A linear time algorithm for the ''k'' maximal sums problem
| title = Mathematical Foundations of Computer Science 2007
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| volume = 4708 | year = 2007 | pages = 442–453 | doi = 10.1007/978-3-540-74456-6_40}}.
*{{citation
| first = T. | last = Takaoka
| title = Efficient algorithms for the maximum subarray problem by distance matrix multiplication
| journal = Electronic Notes in Theoretical Computer Science | volume = 61 | year = 2002
| url = http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf}}.
== External links ==
| 