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

你的益达

发布于 2020-08-05 14:44:41

5960

发布于 2020-08-05 14:44:41

文章被收录于专栏：阿伟的个人博客阿伟的个人博客

问题描述：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

输入: [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

解决方案

定义两个 1 * N的整型数组，记做dp0, dp1。其中N为最大天数，dp0[i]表示在第i天不持有股票的最大收益，dp1[i]表示在第i天持有股票的最大收益。

其转移方程如下：

dp0[i]=max(dp0[i - 1], dp1[i - 1]+price[i])\\\dp1[i]=max(dp1[i - 1], dp0[i - 2]+price[i])

今天不持有情况有两种可能，或者是昨天不持有，或者是昨天持有今天卖了；

今天持有的情况亦有两种，或者是昨天持有，或者是昨天不持有今天买入了，但是需要注意的是题目约束当天卖出后第二天不能买入，也就是说今天要买入不光昨天不能持有，前天亦不能持有。即相当于前天持有的情况在今天卖出去。

baseline如下：

dp0[0] = 0 \\\ dp0[1] = max(0, prices[1] - prices[0]) \\\ dp1[0] = -1 * prices[0] \\\ dp1[1] = max(dp1[0], -1 * prices[1])

实现代码：

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int N = prices.length;
        // dp0[i] 为i天不持有股票的最大收益 ，dp1[i] i天为持有股票最大收益
        int[] dp0 = new int[N];
        int[] dp1 = new int[N];
        dp0[0] = 0;
        dp0[1] = Math.max(0, prices[1] - prices[0]);
        dp1[0] = -1 * prices[0];
        dp1[1] = Math.max(dp1[0], -1 * prices[1]);

        for(int i = 2; i < N; i++){
            dp0[i] = Math.max(dp0[i - 1], dp1[i - 1] + prices[i]);
            dp1[i] = Math.max(dp1[i - 1], dp0[i - 2] - prices[i]);
        }
        return dp0[N - 1];
    }
}

时间复杂度为O（N），额外空间复杂度亦为O（N）。

我们发现当前位置的求解只依赖其前一个和前前一个，因此在递推过程中我们可以只用存储其前一个和前前一个的值完成状态压缩。可以把空间复杂度压缩到O（1），实现代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2){
            return 0;
        }
        int N = prices.length;
        // prePre0 为前天不持有的最大收益, pre0为昨天不持有的最大收益，pre1为昨天持有的最大收益
        int prePre0 = 0;
        int pre0 = Math.max(0, prices[1] - prices[0]);
        int pre1 = Math.max(-1 * prices[0], -1 * prices[1]);
        for(int i = 2; i < N; i++){
            int temp0 = Math.max(pre0, pre1 + prices[i]);
            int temp1 = Math.max(pre1, prePre0 - prices[i]);
            prePre0 = pre0;
            pre0 = temp0;
            pre1 = temp1;
        }
        return pre0;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法