Largest Profit from Daily Stock Data

The problem is to take an array of daily stock prices and find the maximum profit from buying one day and selling on a later day (I assume, you cannot buy and sell on the same day and that you must pick one day to buy and one day to sell).

Basically, my algorithm sets buy dates and walks through the array until a date with a lesser value than the buy date occurs. If there are any dates between the buy date and the lesser value date, then the maximum value on these dates is considered the sell date for that buy date. If there are no dates between the buy date and the lesser value date, then the lesser value date becomes the sell date for the buy date. The lesser value date then becomes the next buy date.

Example 1. As an example, consider this array: 9, 10, 12, 11, 9, 5, 7, 10, 8, 4, 1, 3, 2. This array then becomes [9, 12][5, 10][4, 1][1, 3]. 9 is the first buy date and the first lesser value date is 5, so 12 becomes the first sell date (max value between 9 and 5). 5 becomes the second buy date and the second lesser value date is 4, so 10 becomes the second buy date (max value between 5 and 1). 4 is the third buy date and 1 is the third lesser value date, so 1 becomes the third sell date (no dates in between). Finally, 1 becomes the fourth buy date and there is no fourth lesser value date, so 3 becomes the fourth sell date (max value after 1). Therefore, the max profit is 10-5=5.

Example 2. Consider this array: 10, 8, 7, 4. This array becomes [10, 8][8, 7][7, 4]. 10 is the first buy date, 8 is the first lesser value date, so 8 becomes the first sell date (no dates in between). 8 is the second buy date, 7 is the second lesser value date, so 7 becomes the second sell date (no dates in between). 7 is the third buy date, 4 is the third lesser value date, so 4 becomes the third sell date (no dates in between). Therefore, the max profit is 7-8=-1.

Why does this work?

Let v_n denote the stock price on the nth day, where 0 <= n < N.  Let H be the set of all pairs (B, S) such that:
P1) 0 <= B < N
P2) 0 <= S < N
P3) B < S
P4) For any other values p, q such that:
   i) 0 <= p < N
   ii) 0 <= q < N
   iii) p < q
   Then v_q - v_p <= v_S - v_B

In other words, the Bth and Sth day represent the buy and sell dates respectively that will result in the maximum profit.

Now suppose, we have b, s, e such that:
T1) 0 <= b < N
T2) 0 <= s < N
T3) 0 <= e < N
T4) b < s
T5) s <= e
T6) For every j such that 0 <= j < b, then v_b < v_j
T7) For every j such that b <= j <= e, then v_b <= v_j and v_j <= v_s

Then, only one of the following can be true:
Q1) (b,s) is in H
Q2) For every j, k such that 0 <= j < N, b <= k <= e, (j, k) is not in H

Suppose (b,s) is not in H and there exists j, k such that 0 <= j < N, b <= k <= e where (j, k) is in H.  If (j, k) is in H, then by P3, 0 <= j < k <=e.  By T4, 0 <= j < b or b <= j < k <= e.  Then, by T6 and T7, v_b <= v_j.  By T7, v_k <= v_s.  Let p, q satisfy i), ii) and iii).  Then, v_s - v_b >= v_k - v_j >= v_q - v_p.  Therefore, (b,s) is in H, a contradiction.

Here, I have proven that if we find values b, s, e that satisfy properties 1) - 7), then either (b,s) provides the maximum profit by buying and selling on those days or selling on any days from b to e, including b and e, will not provide the maximum profit.  In other words, selling on any day from b to e, can only yield as much profit as selling on day s.  This allows us to rule out many days as potential selling days.  Also, if s happens to be the day to sell that will yield the most profit, buying on any day from 0 to s - 1, including 0 and s-1, can only yield as much profit as buying on day b.

Source

package algorithm;

/**
 * Assume stock prices are given in an array and you can pick one day to buy and a different day to sell
 * The sell day must be after the buy day
 * What is the profit from the best buy and sell?
 * @author sizu
 *
 */
public class BestBuyAndSell {
 
 public static void main(String[] args) throws Exception {
  int maxProfit1 = findMaxProfit(new int[] {9, 8, 12, 5, 9, 10, 1, 2});
  System.out.println("maxProfit1:"+maxProfit1); // 5
  
  int maxProfit2 = findMaxProfit(new int[] {15, 9, 8, 6, 3});
  System.out.println("maxProfit2:"+maxProfit2); // -1
  
  int maxProfit3 = findMaxProfit(new int[] {9, 8, 12, 5, 9, 10, 1, 15});
  System.out.println("maxProfit3:"+maxProfit3); //14
 }

 private static int findMaxProfit(int[] priceArray) throws Exception {
  if(priceArray.length < 2) {
   throw new Exception ("invalid argument");
  }
  int currentMax = priceArray[1] - priceArray[0]; // Arbitrarily to buy on day 1, sell on day 2
  int min = priceArray[0];
  Integer max = null;
  
  // O(n)
  for(int i=1; i<priceArray.length; i++) {
   int currentVal = priceArray[i];
   if(currentVal < min) {
    if(max != null) {
     int profit = max - min;
     if(profit > currentMax) {
      currentMax = profit;
     }
    } else {
     int profit = currentVal - min;
     if(profit > currentMax) {
      currentMax = profit;
     }
    }
    min = currentVal;
    max = null;
   } else if (max == null) {
    max = currentVal;
   } else if (currentVal > max) {
    max = currentVal;
   }
  }
  if(max != null) {
   int profit = max - min;
   if(profit > currentMax) {
    currentMax = profit;
   }
  }
  
  return currentMax;
 }
}

Output

maxProfit1:5
maxProfit2:-1
maxProfit3:14