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 for a number of days, and the price does not change during a day, 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, for the entire interval we have data for. For example, if we maintain the stock prices in an array, for 4 days (0-3) as follows {10, 8, 12, 11} then we would have made the biggest profit of 4 by buying on day 1 at 8 and selling on day 2 at 12.

The problem has an obvious O(n²) brute force approach solution, an O(?) divide-and-conquer solution and an O(n) iterative solution.

Playground

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