Solution to Problem 3: Gotta Max Profits

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(n-1)/2$ (“n choose 2”) possible subarrays and determine which subarrray has the maximum value. $O(n^2)$ running time.
divide-and-conquer: there’s a divide and conquer algorithm that runs in $O(nlogn)$ time. It’s kind of cool but not as fast as we’d want it to be.
dynamic programming: this solution runs in $O(n)$ time. What would we do without dynamic programming?

Below is the solution (using dynamic programming) to the maxSub array problem in python:

https://gist.github.com/3734606.js

Recurrence relation for maxSub array problem

Given a sequence of $n$ real numbers $A(1) \ldots A(n)$ , determine a contiguous subsequence $A(i) \ldots A(j)$ for which the sum of elements in the subsequence is maximized.