Leetcode188. Best Time to Buy and Sell Stock IV官方解法

女爷i 2023-09-25 15:43 33阅读 0赞

[主站题目链接][Link 1]

[中文站官方解][Link 2]，核心思想是用两个数组buys, sells来记录状态，使用动态规划来解。我后面头昏脑胀地也做出来了，虽然没有优化到极致，但是核心思想与官解是一致的：

## 思路与算法 ##

![在这里插入图片描述][848a3b3b0045419794945c6a76367736.png]

## 细节 ##

![在这里插入图片描述][f3db80ad9ac84c2fa95e454a5bb93dbd.png]

## Java代码： ##

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            if (prices.length == 0) {
        
                return 0;
            }
    
            int n = prices.length;
            k = Math.min(k, n / 2);
            int[][] buy = new int[n][k + 1];
            int[][] sell = new int[n][k + 1];
    
            buy[0][0] = -prices[0];
            sell[0][0] = 0;
            for (int i = 1; i <= k; ++i) {
        
                buy[0][i] = sell[0][i] = Integer.MIN_VALUE / 2;
            }
    
            for (int i = 1; i < n; ++i) {
        
                buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
                for (int j = 1; j <= k; ++j) {
        
                    buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                    sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
                }
            }
    
            return Arrays.stream(sell[n - 1]).max().getAsInt();
        }
    }

![在这里插入图片描述][4ab65417af3c438ca17d3c55923a8a62.png]

## Java代码： ##

class Solution {
        
        public int maxProfit(int k, int[] prices) {
        
            if (prices.length == 0) {
        
                return 0;
            }
    
            int n = prices.length;
            k = Math.min(k, n / 2);
            int[] buy = new int[k + 1];
            int[] sell = new int[k + 1];
    
            buy[0] = -prices[0];
            sell[0] = 0;
            for (int i = 1; i <= k; ++i) {
        
                buy[i] = sell[i] = Integer.MIN_VALUE / 2;
            }
    
            for (int i = 1; i < n; ++i) {
        
                buy[0] = Math.max(buy[0], sell[0] - prices[i]);
                for (int j = 1; j <= k; ++j) {
        
                    buy[j] = Math.max(buy[j], sell[j] - prices[i]);
                    sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);   
                }
            }
    
            return Arrays.stream(sell).max().getAsInt();
        }
    }

## 复杂度分析 ##

![在这里插入图片描述][f9dcce417de846dd863f8f827adac815.png]

[Link 1]: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/
[Link 2]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-iv-by-8xtkp/
[848a3b3b0045419794945c6a76367736.png]: https://img-blog.csdnimg.cn/848a3b3b0045419794945c6a76367736.png
[f3db80ad9ac84c2fa95e454a5bb93dbd.png]: https://img-blog.csdnimg.cn/f3db80ad9ac84c2fa95e454a5bb93dbd.png
[4ab65417af3c438ca17d3c55923a8a62.png]: https://img-blog.csdnimg.cn/4ab65417af3c438ca17d3c55923a8a62.png
[f9dcce417de846dd863f8f827adac815.png]: https://img-blog.csdnimg.cn/f9dcce417de846dd863f8f827adac815.png