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.

O(n²) Brute Force Approach

The stock prices are maintained in an int[n] array with an array element for each of the n days. We loop over the prices, and then in an inner loop we calculate the difference in price between subsequent days and the current day, maintaining the maximum.

public void bruteForce(int[] price) {

  int maxProfit = Integer.MIN_VALUE;
  int buy = -1; // the index of the day we should buy
  int sell = -1; // the index of the day we should sell

  for(int i = 0; i < price.length; i ++) {

    for(int j = i + 1; j < price.length; j ++) {

      // we only compare with price in subsequent days
      int profit = price[j] - price[i];

      if (profit > maxProfit) {
        maxProfit = profit;
        buy = i;
        sell = j;
      }
    }
  }
}

Working code:

Playground MaxProfit.bruteForce()

The time complexity is given by the following sum: (n-1) + (n-2) + ... + 1, which is O(n²).

Divide-and-Conquer

To implement divide-and-conquer, we use the following idea: the profit for a day is given by the difference between the current price and the price in the previous day. As days pass between the buy and sell, the overall profit (or loss) is given by the sum of these daily differences The maximum profit is indicated by the contiguous subarray whose sum of elements returns the maximum possible value. This is the maximum subarray problem.

We need to convert the n-element array price[] into an n-1 element array diff[], which maintains the change in daily price. diff[0] contains the difference in price between day 1 and day 0, diff[1] the difference in price between day 2 and day 1, and so on:

Playground MaxProfit.priceToDiff()

We then process the diff[] array and find the maximum subarray using divide-and-conquer. The indices "s" and "e" indicate the section of the given array to process. "s" indicates the first element and "e" the element immediately following the last element to process, or the end of the array, if the last element to process is the last element of the array. The method returns an int[3], containing, in order:

• the index of the first element of the maximum subarray
• the index of the element following the last element of the maximum subarray. Note that the last element of the maximum subarray is the last element of the array, then the index returned here will fall outside of the array.
• the value of the sum, which is supposed to be maximum for given section [s, e) of the array.

public int[] recursiveMaxSubarray(int[] a, int s, int e)

Playground

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