Max gain

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.

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

Example 1:

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.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Solution

Brutal force way is for each element, scan the rest of the elements to find the max gain, the cost is O(N^2). 

We can find the answer with time cost O(N) and space cost O(1).

scan from array's left to right looking for smallest value as buying price.

Whenever we found a smaller value, there are two cases:

1. Based on the previous buying price, we have achieved max gain, so the lower buying price won't give us better yield.
2. If we based on the new smaller buying price, we can achieve max gain later.

To cover both 2 cases, we need 2 variables the maxGain and minPrice. When we shift to a new minPrice, we need to remember the maxGain achieved so far, and challenge it with later gains based on the new minPrice.

public class MaxGain {
  public static int maxGain(int[] a) {
    int N = a.length; //6
    int maxGain = 0;
    int min = 0;
    //7,1,5,3,6,4
    for(int i = 0; i < N; i++) {  //5
      int gain = a[i] - a[min];  //3
      if(gain > maxGain) {
        maxGain = gain; //5
      } else if(a[min] > a[i]) {
        min = i; //1
      }
    }
    return maxGain;
  }
 
  public static void main(String...args) {
    int[] a = {7,1,5,3,6,4};
    System.out.println(maxGain(a));
  }
}

Time cost O(N), space cost O(1).