Maximum Subarray Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 41: Line 41:
</syntaxhighlight>
</syntaxhighlight>


Working code: {{External|[https://github.com/NovaOrdis/playground/blob/master/data-structures-and-algorithms/maximum-subarray-problem/src/main/java/playground/dsa/maximumSubarrayProblem/MaxProfit.java#L8-L28 Playground MaxProfit.bruteForce()]}}
Working code: {{External|[https://github.com/NovaOrdis/playground/blob/master/data-structures-and-algorithms/maximum-subarray-problem/src/main/java/playground/dsa/maximumSubarrayProblem/MaxProfit.java#L8-L31 Playground MaxProfit.bruteForce()]}}


=Divide-and-Conquer=
=Divide-and-Conquer=

Revision as of 22:21, 9 August 2018

External

Internal

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(n2) brute force approach solution, an O(?) divide-and-conquer solution and an O(n) iterative solution.

O(n2) 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()

Divide-and-Conquer

O(n) Iterative Solution

Playground

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