Global InformationMaximum subarray problem information
In computer science, the maximum sum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum, within a given one-dimensional array A[1...n] of numbers. It can be solved in time and space.
Formally, the task is to find indices and with , such that the sum
![{\displaystyle \sum _{x=i}^{j}A[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3f4ae4590a685044ab6ba7cc8b23cc7c57f5689e)
is as large as possible. (Some formulations of the problem also allow the empty subarray to be considered; by convention, the sum of all values of the empty subarray is zero.) Each number in the input array A could be positive, negative, or zero.[1]
For example, for the array 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.
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 (or the empty subarray, if it is permitted).
- Several different sub-arrays may have the same maximum sum.
Although this problem can be solved using several different algorithmic techniques, including brute force,[2] divide and conquer,[3] dynamic programming,[4] and reduction to shortest paths, a simple single-pass algorithm known as Kadane's algorithm solves it efficiently.
- ^ Bentley 1989, p. 69.
- ^ Bentley 1989, p. 70.
- ^ Bentley 1989, p. 73.
- ^ Bentley 1989, p. 74.