Max Sum in a Sequence of Integers

This algorithm finds the largest sum of any sub-sequence of numbers in a sequence of integers (both positive and negative).

Other interesting cases

4 3 -10 3 -1 2 0 -3 5 7 -4 -8 -10 4 7 -30 -2 -6 4 7 - Mixed positive and negative values

5 5 5 -10 -10 -10 7 7 7 - Positive values at the end

-1 -1 -1 -1 -1 -1 - No positive values

1 2 3 4 5 - All positive values

How the Algorithm Works

Go through the list keeping a running total of the numbers
Find the largest difference between the running totals at any two points
1. Save the minimum running total sum seen so far.
2. Save the biggest difference between a local maximum of the running total and the minimum running total seen so far.
3. The largest sum of a sub-sequence largest of these differences.

Relating to the stock market

A real life example of this problem might be:

Find where you could have made the most money in investing in some stock given the following constraints:

You know how much the that stock went up or down in value each day in the last year.

You could have bought the stock at any point in the year.

You could have sold the stock at any point in the year.

You could have bought and sold the stock at most once.

Knowing that it is best to buy low and sell high, one would examine the graph of the stock price to looks for lows and highs. The best time period to own the stock will be between the low and the high when the stock went up the most. The graph of the stock price is the same running sum of the running sum of the change in value in the stock (with a starting price for the stock). The rules about which maximums and minimums to use reflect that nobody wants to buy the stock at maximum and then sell it at a minimum.

License

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

More converters, calculators, and other JavaScript goodies

ostermiller.org (site index)