【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;
    }
}