Find the Best Run of Trading Days: From Every Range to One Pass

Applying the optimising procedure twice takes the best run of consecutive values from O(n³) to O(n): once to remove duplicated additions, and once to remove work the answer never needed. A market stall records its daily profit and loss over eight days: 5, −7, 4, 2, −3, 6, −8, 3. The owner wants the run of consecutive days with the largest total.

The brute force tries every start and every end, 36 runs for eight days, and adds up the days between, so it is O(n³). Step 1 of the procedure finds the innermost addition dominating, and the waste is duplicated work: the run from day 3 to day 6 re-adds days 3 to 5, which the run before it had just added. A running sum per start removes it, adding one day to the previous total, O(n²). Costing again, the dominant step is now the pair of loops over starts and ends, and the waste is unnecessary work: for each end day, only the start that leaves the largest total matters, and that is the start just after the lowest running total so far. A run's total is a total so far minus an earlier total so far, as in the Prefix Sums topic, so keeping the lowest earlier total gives the best run ending at each day in O(1). Each step below gives a version's additions and best total, from the run.

The one pass keeps three numbers: the total so far, the lowest total so far before today, starting at 0 for the empty run, and the best difference between them. Day by day, from the run:

The best, 9, is the total 7 after day 6 minus the lowest earlier total, −2 after day 2. The best conceivable runtime is O(n), because every day's figure must be read, so after the second removal the procedure stops: 8 additions against 120. A sliding window does not apply, because a window can only be shrunk safely when every value is positive, and losses are negative. The same pass is Kadane's recurrence, in the Dynamic Programming topic in Algorithms, written with totals instead of the best run ending at each day.