自学内容网 自学内容网

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)!