LeetCode 188题： 买卖股票的最佳时机IV优化（原创）

之前完成了LeetCode 188题： 买卖股票的最佳时机IV（原创）-CSDN博客，虽然完成代码编写，并提交成功，但运行效率还未达到最优的1ms，见下图：

仔细检查代码，感觉还是有可优化的点：

1.  由于只需要返回最后一天的最大获利值，因此之前所有天数的最大获利值不需要存储；
2. 不能连续够买，也意味着没法连续卖，因为手头上最多只有一只股票；
3. 必须先买才能后卖，因此第n次卖的操作是基于第n次买的操作基础上；而第n次买的操作是基于第n-1次卖的操作，
4. 另外，第一次买的的操作属于特殊情况，因为没有上一次卖的操作，获利值等于-prices[0]

按照这个思路完成代码修改，修改之后的代码如下：

package dp;

public class MaxProfit4 {

    public static void main(String[] args) {
        int[] prices = {3, 2, 6, 5, 0, 3};
        int k = 2;
        int result = new MaxProfit4().maxProfit(k, prices);
        System.out.println("计算结果：" + result);
    }

    public int maxProfit(int k, int[] prices) {
        int[] buys = new int[k];
        int[] sells = new int[k];
        for (int i = 0; i < k; i++) {
            buys[i] = -prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < k; j++) {
                // j-1天卖掉的获利值，第1天为0
                int sellJMinus1 = j > 0 ? sells[j - 1] : 0;
                // 买了j次的最大获利值等于：昨天买了j次，和昨天卖了j-1次，今天再买的最大值
                buys[j] = Math.max(buys[j], sellJMinus1 - prices[i]);
                // 卖了j次的最大获利值等于：昨天卖了j次，和昨天买了j次，今天再卖掉的最大值
                sells[j] = Math.max(sells[j], buys[j] + prices[i]);
            }
        }
        return sells[k - 1];
    }
}

提交之后果然性能优化到1ms，见下图：

原文地址：https://blog.csdn.net/IT_Fly/article/details/140573933

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！