Another way of the stating the problem is: determine the maximum value subarray from the array of “crude” stock price changes. This is reducible to the maximum value subarray problem (oh yeah!).
There are three known ways (specific to my knowledge thus far) of solving this problem:
- brute-force: list all (“n choose 2”) possible subarrays and determine which subarrray has the maximum value. running time.
- divide-and-conquer: there’s a divide and conquer algorithm that runs in time. It’s kind of cool but not as fast as we’d want it to be.
- dynamic programming: this solution runs in time. What would we do without dynamic programming?
Below is the solution (using dynamic programming) to the maxSub array problem in python:
Recurrence relation for maxSub array problem
Given a sequence of real numbers , determine a contiguous subsequence for which the sum of elements in the subsequence is maximized.
For any and where
= Maximum sum over all windows ending at .
= . So either we extend the optimal window ending at or start a fresh window with .