Reference: LeetCode
Difficulty: Easy

My Post: Java Solution with Comments and Explanation (BF, Divide and Conquer, One-Pass)

Problem

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Constraint: Note that you cannot sell a stock before you buy one.

Example: 

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Analysis

Brute-Force

For each day i, compare its prices with the following price of each day j, and update the maximum profit.

Note:

  • j should starts from 0.
  • maxProfit should be initialized with $0$.
1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
  int maxProfit = 0;  // profit can't be negative
  for (int i = 0; i < prices.length; ++i) {
    for (int j = i; j < prices.length; ++j) {
      maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
    }
  }
  return maxProfit;
}

Time: $O(N^2)$
Space: $O(1)$

Divide and Conquer

We divide the problem into two subproblems left and right. Then we calculate:

  • The best buy time B1 and the best sell time S1 from left.
  • The best buy time B2 and the best sell time S2 from right.
  • The time M1 of minimum price and the time X1 of maximum price in left.
  • The time M2 of minimum price and the time X2 of maximum price in right.

In the combine step, we have three cases to consider:

  • Case 1: In left, we buy at B1 and sell at S1.
  • Case 2: In right, we buy at B2 and sell at S2.
  • Case 3: In left and right, we buy at M1 and sell at X2.
    • We cannot use B1 and S2 because B1 may not be the time of minimum price and S2 may not be the time of maximum price. Check out the illustration below.
  • Beside, we need to update the time of minimum price and maximum price.

Here is an illustration of the text above. Notice the left is P1 and right is P2.

The following solution uses a helper class BuySell to encapsulate variables passed across recursive levels.

1
2
3
4
5
6
7
8
9
private class BuySell {
  int buyTime; int sellTime;
  int minTime; int maxTime;
  
  BuySell(int b, int s, int min, int max) {
    buyTime = b; sellTime = s;
    minTime = min; maxTime = max;
  }
}

Here is the main part of the solution. Notice that it is a good approach to separate the combining code from the recursive function. It makes code more readable.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public int maxProfit(int[] prices) {
  if (prices == null || prices.length == 0) {
    return 0;
  }
  BuySell result = maxProfit(prices, 0, prices.length - 1);
  return prices[result.sellTime] - prices[result.buyTime];
}

// helper
private BuySell maxProfit(int[] prices, int lo, int hi) {
  if (lo >= hi) { // base case: only one time
    return new BuySell(lo, lo, lo, lo);
  }
  int mid = lo + (hi - lo) / 2; // divide
  BuySell left = maxProfit(prices, lo, mid); //conquer
  BuySell right = maxProfit(prices, mid + 1, hi);
  return combine(prices, left, right);
}

private BuySell combine(int[] prices, BuySell left, BuySell right) {
  // case 1: left
  int maxProfit = prices[left.sellTime] - prices[left.buyTime];
  int bestBuyTime = left.buyTime;
  int bestSellTime = left.sellTime;
  
  // case 2: right
  int case2Profit = prices[right.sellTime] - prices[right.buyTime];
  if (case2Profit > maxProfit) {
    maxProfit = case2Profit;
    bestBuyTime = right.buyTime;
    bestSellTime = right.sellTime;
  }
  
  // case 3: left.minTime, right.maxTime
  int case3Profit = prices[right.maxTime] - prices[left.minTime];
  if (case3Profit > maxProfit) {
    maxProfit = case3Profit;
    bestBuyTime = left.minTime;
    bestSellTime = right.maxTime;
  }
  
  // update min and max
  int newMinTime = (prices[left.minTime] < prices[right.minTime]) ? left.minTime : right.minTime;
  int newMaxTime = (prices[left.maxTime] > prices[right.maxTime]) ? left.maxTime : right.maxTime;
  
  return new BuySell(bestBuyTime, bestSellTime, newMinTime, newMaxTime);
}

Time: $O(N)$ since $T(N) = 2T(N) + O(1)$
Space: $O(\log{N})$ because of the call stack.

One-Pass

Notice that the maximum profit that can be made by selling on a specific day is determined by the minimum of the stock prices over the previous days. Thus, we can loop over each price in prices, and keep updating the minimum price and at the same update the maximum profit.

Note: The ordering of updating maxProfit and minPrice does not matter.

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
  int maxProfit = 0;
  int minPrice = Integer.MAX_VALUE;
  for (int price : prices) {
    maxProfit = Math.max(maxProfit, price - minPrice);
    minPrice = Math.min(minPrice, price);
  }
  return maxProfit;
}

Time: $O(N)$
Space: $O(1)$