Best Time to Buy and Sell Stock problem

题

Best Time to Buy and Sell Stock
Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock IV

题解

k=1
当最多只能交易一次时，思路如下：
Say the given array is:
[7, 1, 5, 3, 6, 4]
If we plot the numbers of the given array on a graph, we get:

维护两个变量：minprice代表到目前为止，股票的最低价格；maxprofit代表在最多交易一次的情况下，所能获取的最大利益。

public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }
}

k>1
k=1的情况下比较简单，Best Time to Buy and Sell Stock III是Best Time to Buy and Sell Stock IV的特例，因此，我们研究下k>1的情况即可，找到一个通解。

看完Buy/Sell Stock With K transactions To Maximize Profit Dynamic Programming即可理解此过程。

Best Time to Buy and Sell Stock III leetcode题解给出了详细的解答过程，如下：
DP recursive formula:
dp[k, i] = max(dp[k, i-1], prices[i] - prices[j] + dp[k-1, j-1]), j=[0..i-1]

For k transactions, on i-th day,
if we don’t trade then the profit is same as previous day dp[k, i-1];
and if we bought the share on j-th day where j=[0..i-1], then sell the share on i-th day then the profit is prices[i] - prices[j] + dp[k-1, j-1] .
Actually j can be i as well. When j is i, the one more extra item prices[i] - prices[j] + dp[k-1, j] = dp[k-1, i] looks like we just lose one chance of transaction.

So the straigtforward implementation is:

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

Time complexity is O(kn^2), space complexity is O(kn).

In the above code, min is repeated calculated. It can be easily improved as:

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

Time complexity is O(kn), space complexity is O(kn).

如果想获取整个股票交易的过程，可参考StockBuySellKTransactions.java中的代码。

拿张纸，画出动态规划的过程，即可深刻理解该题。

参考资料：

文章目录

题

题解