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 .

**Chao!**

Advertisements