Harvest Software - Programming - Algorithm

C/C++
Algorithm
Data Structure
UVA Hints
UVA Problem Ranking
Tip and Trick

Maximum Subvector Problem

Problem Description

Given n integers a1,a2,...,an. Define S(i,j) = ai + ... + aj, where i <= j. What is the maximum value of S(i,j) ?

Brute Force Approach

maxsum = 0
for i = 1 to n
    for j = i to n
         maxsum = max( compute S(i,j), maxsum )

Computing S(i,j) takes O(n) and we have 2 loops running. So total running time of this algorithm is O(n^3).

If we observe carefully, S(i,j) can be computed in O(1) time by precomputation.

Denote sum[i] = a1 + a2 + ... + ai
We can precompute sum[i] in O(n) time
and observe that S(i,j) = sum[i] - sum[j-1]

// compute sum[i]
sum[0] = 0;
for i = 1 to n
    sum[i] = sum[i-1] + ai

// compute maxsum
maxsum = 0
for i = 1 to n
     for j = i to n
          maxsum = max( sum[i] - sum[j-1], maxsum)

Computing sum[i] takes O(n) and computing maxsum takes O(n^2). So, total running time for the improved version is O(n^2 + n) = O(n^2)

Can we do better ? - Scan algorithm

Scan Algorithm

maxsum = sum = 0;
for i = 1 to n
     sum = max( sum + ai, 0 )
     maxsum = max( sum, maxsum )

This algorithm runs in linear time O(n). The question is, can you prove that this algorithm is indeed correct?

Rough Proof

"sum" is accumulated sum until position i (i.e, a1 + a2 + ... + ai). If sum is negative, it will cause us a disadvantage and we should try new sequence, but as long as the sum is positive it will cause us advantage, so why don't we include them.