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

冷不防 2021-09-30 03:56 240阅读 0赞

题目：

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

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

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

分析：

由于你不能同时进行多次交易，咱们可以说要找到交易额度最大的单次交易，并且这些交易不能够在连续的天数进行。那么咱们就只需要找到当前天数之前的最大利润值并和当前利润相加，就是但前天数最大利润值。

代码：

1 //35ms 10% 暴力。。。真的是惨
     2 class Solution {
     3     public int maxProfit(int[] prices) {
     4         if(prices.length<2)
     5             return 0;
     6         int len=prices.length;
     7         int[] max=new int[len];
     8         max[0]=0;
     9         max[1]=prices[1]-prices[0]>0?prices[1]-prices[0]:0;
    10         for(int n=2;n<len;++n) {
    11             max[n]=max[n-1];
    12             for(int m=0;m<=n;++m) 
    13                 if(m<2)
    14                     max[n]=max[n]>prices[n]-prices[m]?max[n]:prices[n]-prices[m];
    15                 else
    16                     max[n]=max[n]>prices[n]-prices[m]+max[m-2]?max[n]:prices[n]-prices[m]+max[m-2];
    17         }
    18         return max[len-1];
    19     }
    20 }

这是我写的代码...可以说就是暴力破解了。我遍历当前天数之前的所有天数，并将得到的利润相加的到一个当前天数最大的利润。

我再贴一段代码：

1 //8ms 100% 看看人家的 这是leetcode所有解答中运行速度最快的代码
     2 class Solution {
     3     public int maxProfit(int[] prices) {
     4         if(prices.length==0)return 0;
     5         int[] dp1=new int[prices.length];
     6         int[] dp2=new int[prices.length];
     7         dp2[0]=0;
     8         dp1[0]=-prices[0];
     9         for(int i=1;i<prices.length;i++){
    10             dp1[i]=Math.max(dp1[i-1],i>=2?dp2[i-2]-prices[i]:-prices[i]);
    11             dp2[i]=Math.max(dp2[i-1],dp1[i-1]+prices[i]);
    12         }
    13         return dp2[prices.length-1];
    14     }
    15 }

我倒腾了一会才明白他到底写了什么，dp1存储的是当前天数进行了买入交易后得到的金额，dp2存储的是将当前天数买入后可以得到的最大金额，当然如果dp1当前买入的金额较大并且有上次的股票并未交易完，那么他是不会买入当前天数股票的，dp2同理，如果按当天金额卖出股票无法获得利润，他是不会卖出去的。

转载于:https://www.cnblogs.com/CHAHA123/p/10665229.html