121. Best Time to Buy and Sell Stock

Leetcode Array Dynamic Programming

Say you have an array for which the $i^{th}$ 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.

分析

这道题目考查的是基本的动态规划。可以试着这么想：maxProfits[$i$]代表前$i$天的最大利润，那么怎么知道前$i+1$天的最大利润maxProfits[$i+1$]呢？什么情况下可以获得最大利润？显然是最低点买入，最高点卖出。既然求前$i+1$天的最大利润，则第$i+1$天肯定不能买入，不然不能卖出。那么第$i+1$天所做的事情仅有卖出，那么第$i+1$天卖出的股价减去前第$i$天的股票最低点，就有可能是$i+1$天的最大利润。

分析到这里，动态规划的方程非常明显了：

maxProfits[i] = max(maxProfits[i - 1], prices[i - 1] - minPrices[i]);

前i天的最大利润 = max(前i-1天的最大利润，第i天卖出)

相应的代码：

public int maxProfit(int[] prices) {
    int[] maxProfits = new int[prices.length + 1];
    int[] minPrices = new int[prices.length + 1];
    maxProfits[0] = 0; minPrices[0] = Integer.MAX_VALUE;
    for (int i = 1; i < maxProfits.length; i++) {
        minPrices[i] = Math.min(minPrices[i - 1], prices[i - 1]);
        maxProfits[i] = Math.max(maxProfits[i - 1], prices[i - 1] - minPrices[i]);
    }
    return maxProfits[prices.length];
}

由于股票价格是一维的，而且最终只需要截止到最后一天的最大利润，中间结果可以不用保存：

public int maxProfit(int[] prices) {
    int maxProfits = 0;
    int minPrices = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {
        if (prices[i] < minPrices) minPrices = prices[i];
        if (prices[i] - minPrices > maxProfits) maxProfits = prices[i] - minPrices;
    }
    return maxProfits;
}

这样的算法时间复杂度是$O(n)$，空间复杂度是$O(1)$。