Indian Computing Olympiad

Computing Prefix Sums

One dimension: Maximum sum subsection

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² 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³.

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³ to N².

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.)