【LeetCode練習】[困難]123. 買賣股票的最佳時機 III

【LeetCode練習】[困難]123. 買賣股票的最佳時機 III

leetcode中還有

買賣股票的最佳時機I

買賣股票的最佳時機II

I，II 具體内容

123. 買賣股票的最佳時機 III

123. 買賣股票的最佳時機 III

算法思想：dp

題目：

leetcode官方解答

java代碼

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = -prices[0];
        int buy2 = -prices[0];
        int sell1 = 0;
        int sell2 = 0;
        for (int i = 1; i < prices.length; i++){
            buy1 = Math.max(buy1,-prices[i]);
            sell1 = Math.max(sell1,buy1+prices[i]);
            buy2 = Math.max(buy2,sell1-prices[i]);
            sell2 = Math.max(sell2,buy2+prices[i]);
        }
        return sell2;
    }
}
           

123. 買賣股票的最佳時機 IV

123. 買賣股票的最佳時機 IV

算法思想：dp

題目：

java代碼

class Solution {
    public int maxProfit(int k, int[] prices) {
        if(k < 1){
            return 0;
        }
        //交易次數過多，直接退化成， 任意交易次數，使得收益最大
        if(k >= prices.length/2) {
            return maxProfit2(prices);
        }
        //每一筆交易,有K*2個狀态
        int[] buy = new int[k+1];//buy[i]:表示第i次買入
        int[] sell = new int[k+1];//sell[i]:表示第i次賣出
        Arrays.fill(buy, Integer.MIN_VALUE);//初始化
        /**
         * 高手解答：
         * 借助股票問題，再次回扣一種極為普遍的dp定義： 考慮前XX種情況，滿足YY條件以及ZZ條件能夠達到的最值。
         * 同時引申出，為什麼後邊要區分有沒有股票的情況，能不能不區分就把這個題做出來。
         * 這道題我們不妨直接做這麼個定義：考慮前n支股票，最多交易k次能夠獲得的最大利潤。sell[k]
         * 好了，基于這個定義，我們知道，最大利潤實際上就意味着手上不能有股票，否則就不叫最大利潤。
         * 那麼不難推出下面這個dp的狀态轉移，這實際上還是基于0-1背包問題，即：賣不賣第i支股票。
         *
         * 1.如果不賣第i支股票，那麼很簡單，你既然不賣了，那我也不關心手裡有沒有股票了，
         * 我可以考慮前i-1個股票最多賣k次，也就是sell[k]
         * 2.如果你要賣第i支股票，那麼就比較複雜了，因為你得先有一隻股票，
         * dp數組描述的是沒有股票的最值情況，是以你是不知道**有股票**的情況下，
         * 考慮前i-1個股票，在最多賣k-1次的最大利潤的。
         */
        /**
         * 注意：
         * 無論題目中是否允許「在同一天買入并且賣出」這一操作，
         * 最終的答案都不會受到影響，這是因為這一操作帶來的收益為零。
         * buy[],sell[]中存放的目前狀态中能帶來的最大收益
         */
        for (int i = 0; i < prices.length; i++){//買入要看上一次賣出,賣出要有買入
            for (int j = 1; j < k+1; j++){
                buy[j] = Math.max(buy[j], sell[j-1]-prices[i]);//買入,要将之前的賣掉,sell[i-1]前一次賣出的最大收益
                sell[j] = Math.max(sell[j], buy[j]+prices[i]);//賣出,之前買入的收益加上賣出股票價格
            }
        }
        return sell[k];
    }

    public int maxProfit2(int[] prices) {
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++){
            if (prices[i] > prices[i-1]){
                maxProfit += prices[i]-prices[i-1];
            }
        }
        return maxProfit;
    }
}