写作网站推荐,网站开发的岗位与分工,网站开发专业实习报告,网页编辑软件免费版给定一个整数数组#xff0c;其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下#xff0c;你可以尽可能地完成更多的交易#xff08;多次买卖一支股票#xff09;:
你不能同时参与多笔交易#xff08;你必须在再次购买前…给定一个整数数组其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下你可以尽可能地完成更多的交易多次买卖一支股票:
你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 卖出股票后你无法在第二天买入股票 (即冷冻期为 1 天)。 示例:
输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
思路与之前的股票题大致相同加了冷冻期
冷冻期出现在刚刚卖掉股票之后无法立即买入所以只影响dp[i][1]的状态
dp[i][1]Math.max(dp[i-1][1], dp[i-2][0]-prices[i]);
将dp[i][1]的影响因素由一台前无股票状态改为两天前无股票状态
提交的代码
class Solution { public int maxProfit(int[] prices) { if(prices.length0) { return 0; } int dp[][] new int[prices.length][2]; dp[0][0] 0; dp[0][1] -prices[0]; for(int i1;iprices.length;i) { if(i 1) { dp[1][0] Math.max(dp[0][0],dp[0][1]prices[i]); dp[1][1] Math.max(dp[0][1], dp[0][0]- prices[i]); continue; } dp[i][0] Math.max(dp[i-1][0], dp[i-1][1]prices[i]); dp[i][1]Math.max(dp[i-1][1], dp[i-2][0]-prices[i]); } return dp[prices.length-1][0]; }
}
