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[i];

        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.