The maximum subarray problem

Unsolved Easy Archive

archive posted 2 Jul 2026

Given an array of $n$ integers, some possibly negative, find a contiguous subarray with the largest sum. For example, in $[- 2, 1, - 3, 4, - 1, 2, 1, - 5, 4]$ the best subarray is $[4, - 1, 2, 1]$ with sum 6. Give an $O (n)$ algorithm and prove it correct.

Posed by Ulf Grenander, 1977

Like0

algorithms dynamic-programming

History and references

Solved by Jay Kadane.

Ulf Grenander proposed the problem in 1977 as a simplified model for detecting patterns in digitized images. Grenander had an $O (n^{2})$ method, Michael Shamos found an $O (n lo g n)$ divide-and-conquer algorithm, and Jay Kadane then found a linear-time algorithm after hearing Shamos describe the problem at Carnegie Mellon. Jon Bentley told the story in his Programming Pearls column in Communications of the ACM in 1984. Kadane's algorithm scans from left to right and keeps the best sum of a subarray ending at the current position, which is either the current element alone or the current element plus the previous best. The answer is the largest of these running values.

References

Maximum subarray problem (Wikipedia)

Solutions 0

Nobody has posted a solution here yet. Solutions written on Problempedia are credited to the people who write them.

References

Solutions 0

Discussion 0