如何制作wordpress网站地图,全景旅游网站项目建设,竞价托管公司,小型生鲜超市店面设计1. 题目
给定一个数组#xff0c;它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易#xff08;你必须在再次购买前出售掉之前的股票#xff09;。
示例 1:
输入: […1. 题目
给定一个数组它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天股票价格 0的时候买入
在第 6 天股票价格 3的时候卖出
这笔交易所能获得利润 3-0 3 。随后在第 7 天股票价格 1的时候买入在第 8 天 股票价格 4的时候卖出这笔交易所能获得利润 4-1 3 。示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天股票价格 1的时候买入
在第 5 天 股票价格 5的时候卖出,
这笔交易所能获得利润 5-1 4 。 注意你不能在第 1 天和第 2 天接连购买股票之后再将它们卖出。 因为这样属于同时参与了多笔交易你必须在再次购买前出售掉之前的股票。示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。来源力扣LeetCode 链接https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 121. 买卖股票的最佳时机 LeetCode 122. 买卖股票的最佳时机 II LeetCode 188. 买卖股票的最佳时机 IV动态规划 LeetCode 309. 最佳买卖股票时机含冷冻期动态规划 LeetCode 714. 买卖股票的最佳时机含手续费DP
dp[i][k][0]表示第 i 天经过最多 k 次交易0不持有股票的最大收益dp[i][k][1]表示第 i 天经过最多 k 次交易1持有股票的最大收益最后应该返回的是dp[n-1][k][0]最后持有股票收益是负的所以不是1k 定义是买入的时候增加 1次i 0 时不持有股票dp[i][k][0]0持有股票dp[i][k][1]-prices[0]i 0 时 dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1]prices[i]) 不持有股票--------- 前一天没持有 or 前一天持有然后卖出 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]) 持有股票--------- 前一天持有 or 前一天不持有然后买入交易k1
class Solution {
public:int maxProfit(vectorint prices) {if(prices.empty())return 0;int i, j, k, n prices.size(), maxt 2;vectorvectorvectorint dp(n,vectorvectorint(maxt1,vectorint(2,0)));for(i 0; i n; i){for(k 1; k maxt; k){if(i0){dp[i][k][0]0;dp[i][k][1]-prices[0];continue;}dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1]prices[i]);dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i]);}}return dp[n-1][maxt][0];}
};该模板可以解股票第1题maxt 1该模板可以解股票第2题maxt n最后一个例子超时n^2 复杂度该模板可以解股票第4题(第2题第3题的组合)
56 ms 21.4 MB
