random memes }

Algorithm - Find Greatest Sequence

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.

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.