Maximum Subarray Problem

External

• CLRS page 68

Internal

• Data Structures and Algorithms

Overview

The maximum subarray problem is useful to solve the following problem:

Assuming we have access to stock prices of a company at the close of market for a number of days, determine what would have been the best day to buy and the best day to sell one unit of stock to make the maximum profit.

If we maintain the stock prices in an array, for 4 days (0-3) as follows price[0] = 10, price[1]=8, price[2]=12 and price[3]=11, then we would have made the most profit buying on day 1 at 8 and selling on day 2 at 12 (profit of 4).

Playground

https://github.com/NovaOrdis/playground/tree/master/data-structures-and-algorithms/maximum-subarray-problem