This algorithm finds the largest sum of any sub-sequence of numbers in a sequence of integers (both positive and negative).
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
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.
- 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.
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.
Copyright Stephen Ostermiller 2006-2014