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).

Enter any sequence of integers (separated by spaces or commas):

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

  1. Go through the list keeping a running total of the numbers
  2. 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:
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)

Copyright Stephen Ostermiller 2006-2014