Find the maximum interval sum in a list of real numbers

The complexity is just O(n) for Kadane's algorithm:

The algorithm keeps track of the tentative maximum subsequence in (maxSum, maxStartIndex, maxEndIndex). It accumulates a partial sum in currentMaxSum and updates the optimal range when this partial sum becomes larger than maxSum.

It's O(N):

int sum = 0;
int M = 0;  // This is the output
foreach (int n in input)  {
  sum += n;
  if (sum > M)
      M = sum;

  if (sum < 0)
    sum = 0;
}

The idea is to keep the sum of all integers that have been encountered since last reset. A reset occurs when the sum goes below zero - i.e. there are too many negative numbers in the current interval to make it possibly the best one.

This is a classical, well known, problem that is an excellent eye-opener in any algorithm course. It is hard to find a better/simpler starter. You can find an n*3-, n*2-, nlogn- and even the simple n-algorithm.

I found the problem discussed/solved in John Bentley´s "Programming Pearls" from 1986 - and did use it for years as a starter in our Algorithm Course at NTNU/Trondheim. Some 20 years ago I first used it in an examination for about 250 students, where just 1 student did discover all the 4 solutions, see above. He, Bjørn Olstad, became the "youngest professor ever" at NTNU in Trondheim, and has still this status beside heading the MSFT search division in Oslo. Bjørn also took the challenge to find good practical applications of the algorithm. Do you see some?

• Arne Halaas