Given a sequence of integers, a subsection is a block of contiguous integers in the sequence. For instance, here is a sequence and a subsection marked out whose sum is -1.

3 -1 2 -1 2 -3 4 -2 1 2 1 |<---- ------>| sum = -1

The task is to find the subsection whose sum is maximum.

**Solution**

*Naive solution*

Let the sequence be A[1], A[2], …, A[N]. Pick each possible pair of positions (i,j) and compute the sum of the subsection from A[i] to A[j].

There are N^{2} such choices for (i,j) and we
need to scan the length of the subsection, which requires
work proportional to N in general. Overall, this takes
time N^{3}.

*Smarter solution*

For each position i, compute the prefix sum A[1] + A[2] + … + A[i]. Let PrefSum[i] denote this value. We can compute PrefSum[i] for each i in a single scan, since PrefSum[i+1] is PrefSum[i] + A[i+1].

Now, for each pair (i,j), we get the sum of this subsection as PrefSum[j] - PrefSum[i], which takes constant time.

Thus, the overall problem comes down in complexity from
N^{3} to N^{2}.

Actually, we can even smarter. This problem can actually be solved in time proportional to N.

Let `Best(i)` denote maximum sum segment ending at
i. Then, we have the following recursive definition.

Best(i) = max { A[i], // Best segment starts here A[i] + Best(i-1) // Best segment extends previous } Best(1) = A[1]

This can be computed efficiently in time proportional to N using dynamic programming.

Note that we have have assumed that subsections are of
length greater than 0. If zero length segments are
permitted, we also have to include a term 0 to
the `max` computation when
determining `Best(i)`. (For instance, if all
values are negative, the maximum sum subsection would
then be the empty subsection with sum 0.)

©IARCS 2012–2016

PÄ›stujeme web | visit: Skluzavky