dtcms模板 java Zookeeper使用 vim centos7 selenium nhibernate insert linux自动获取ip 完美解决cpu利用率低 java微服务架构 linuxmysql启动命令 python在线教程 python链接mysql数据库 python正则匹配空格 java教学 java数据类型 java查找字符串 java手册 java入门代码 java基本数据结构 java中的泛型 javascript源代码 苹果5s降级 倒计时计时器 pr滤镜插件 js转int linux多线程编程 firework下载 野德天赋 findall 微信猜拳 apihook ocr文字识别软件免费下载 igfxpers 影音先锋下载速度慢 刷新当前页面 ae烟雾特效 强制换行快捷键 python常用函数
当前位置: 首页 > 学习教程  > 编程语言

LeetCode309-最佳买卖股票时机含冷冻期

2020/8/11 20:48:29 文章标签:

LeetCode309-最佳买卖股票时机含冷冻期

题目

解法

动态规划
dp[i][j]中,i是日期,j是状态。
状态:
dp[i][0]: 手上不持有股票,并且不在冷冻期中的累计最大收益
dp[i][1]: 手上持有股票的最大收益
dp[i][2]: 手上不持有股票,并且处于冷冻期中的累计最大收益(卖出当天就算冷冻期)

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0;
        int n = prices.length;
        if(n==2) return prices[0]<prices[1]?prices[1]-prices[0]:0;
        int[][] dp = new int[n][3];
        //0是不持有也不是冷冻期,1是持有,2是冷冻期
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;

        for(int i = 1 ; i < n ; ++i){
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][2]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = dp[i-1][1]+prices[i];
        }
        return Math.max(dp[n-1][0],dp[n-1][2]);
    }
}

空间优化

class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }

        int n = prices.length;
        int f0 = -prices[0];
        int f1 = 0;
        int f2 = 0;
        for (int i = 1; i < n; ++i) {
            int newf0 = Math.max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = Math.max(f1, f2);
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }

        return Math.max(f1, f2);
    }
}

本文链接: http://www.dtmao.cc/news_show_100412.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?