Someone posted a weblog entry (do not remember where) with a puzzle:
How to efficiently find a subsequence of values with the greatest sum within a larger sequence. </p>
The simplest algorithm is to try all subsequences. This runs in time O(N\^3), so is not useful except for very small sequences (say 100 or much less).
For some reason this problem stuck with me until I came up with an
efficient O(N) algorithm. The basic notion is to first collapse runs
like-signed to a single number. Next the sequence is scanned for triples
that can be collapsed (either positive or negative), and the scan is
repeated until no more triples can be combined. (Think of drops of
condensation beading together.)
Attached an archived Eclipse project containing the implementation and tests.
NOTE 2016.07.01: The formerly attached code is lost. Could be easily re-created from the above description.