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:

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.

For any i and j where 1 <= i <= j <= n
M(j) = Maximum sum over all windows ending at j.

M(j) = max \{ M(j-1) + A[j], A[j] \}. So either we extend the optimal window ending at j or start a fresh window with A[j].

Chao!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s