Question:

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.

Thinking:

  • Method1:
    • 使用遍历，可以ac，但是速度很慢。
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if(prices == null || prices.length == 0)
            return result;
        int len = prices.length;
        for(int i = 0; i < len - 1; i++){
            for(int j = i + 1; j < len; j++)
                result = Math.max(result, prices[j] - prices[i]);
        }
        return result;
    }
}
  • Method2:
    • 计算每一天的最大profit需要些什么？
      • 能得到的最低买入价。(Math.min(minPrice, prices[i]))
      • 当天如果卖出的收益。(prices[i] - minPrice)
      • 以前卖出的最大收益。
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        if(prices == null || prices.length == 0)
            return result;
        int maxPro = 0;
        int minPrice = Integer.MAX_VALUE;
        int len = prices.length;
        for(int i = 0; i < len; i++){
            minPrice = Math.min(minPrice, prices[i]);
            maxPro = Math.max(maxPro, prices[i] - minPrice);
        }
        return maxPro;
    }
}
  • Method 3: DP
    • 维护两个变量，一个是当天出售可以赚到的最大值，一个是全局的最大值。
class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        int local = 0, global = 0;
        for(int i = 1; i < prices.length; i++){
            local = Math.max(0, local + prices[i] - prices[i - 1]);
            global = Math.max(global, local);
        }
        return global;
    }
}

二刷

参考了一刷时候Method3

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0) return 0;
        int local = 0, global = 0;
        for(int i = 1; i < prices.length; i++){
            local = Math.max(0, local - prices[i - 1] + prices[i]);
            global = Math.max(global, local);
        }
        return global;
    }
}

Third time

  1. This time I beat 100%, for each day, we have fixed price, we need to find the minimum price ahead.
    • Update the max profit.
    • Update the min price. 
      class Solution {
 public int maxProfit(int[] prices) {
  if(prices == null || prices.length == 0) return 0;
  int min = prices[0], profit = 0;
  for(int i = 0; i < prices.length; i++){
      profit = Math.max(profit, prices[i] - min);
      min = Math.min(min, prices[i]);
  }
  return profit;
 }
}

Amazon session

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length <= 1) return 0;
        int res = 0, min = prices[0];
        for(int i = 1; i < prices.length; i++){
            res = Math.max(res, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return res;
    }
}