Maximum Contiguous Sum

I have been reading Programming Pearls by Jon Bentley. It’s an old school book about programming. One of the problem posed by is from image processing, to find the maximum contiguous sum:

For an input vector x of n [integers]; the output is the maximum sum found in any contiguous subvector of the input.

For instance, if the input vector contains these ten elements: (31, -41, 59, 26, -53, 58, 97, -93, -23, 84) then the program returns the sum of x[2…6], or 187. The problem is easy when all the numbers are positive; the maximum subvector is the entire input vector. The rub comes when some of the numbers are negative: should we include a negative number in hopes that positive numbers on either side will compensate for it? To complete the problem definition , we’ll say that when all inputs are negative the maximum-sum subvector is the empty vector, which has sum zero.

Its straight forward to find an inefficient solution, but harder to find a solution which copes well with large n.The idea for my solution is shown in the picture. Loop through the vector adding up the values as you go, making the sum. Keep track of the minimum sum so far. If the difference between rolling sum and the minimum sum is a new best value, update the best value.

private int Mcs(int[] vec)
{
    int minSum = 0;
    int bestSum = 0;
    int sum=0;
    for (int i = 0; i < vec.Length; i++)
    {
        sum += vec&#91;i&#93;;

        if (sum < minSum)
            minSum = sum;
                
        if ((sum - minSum) > bestSum)
            bestSum = sum - minSum;
    }

    return bestSum;
}

It’s not ground breaking stuff, but I was pleased all the same to find an O(n) solution.

2 thoughts on “Maximum Contiguous Sum

  1. Rather than getting to a one-page website with graphics from the 90’s and wondering if you should really cough up your credit
    card number to this site, then waiting two weeks for a response from
    their customer service team, you get professionalism
    all the way (if you choose the right VPN service, of course).
    * Load balancing – This feature will suggest a server with the least users once a certain location comes with multiple servers.
    The PPTP is known best for faster speeds and bandwidth efficiency.

  2. I have been in most of the cathedrals of Rome and Sicily (some of which I never want to go in again), but I had not remembered visiting this one.

Leave a Reply

Your email address will not be published. Required fields are marked *