【Leetcode】Best Time to Buy and Sell Stock III.pdf

为为梦梦起起航航 不不积积小小流流无无以以成成江江海海 【【LLeeeettccooddee】】BBeesstt TTiimmee ttoo BBuuyy aanndd eellll ttoocckk IIIIII 分类： leetcode 动态规划 2013-12-15 17:46 239人阅读 评论 (0) 收藏 举报 动态规划最大收益C++leetcode Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock efore you uy again). 题意：获取股票最大收益，最多可交易两次，且必须完成一桩交易之后才能 进行另一桩交易。当然，可以第i天卖出后又当天买回。 因为最多两次交易，很容易联想到将数组分为两部分，对两部分数组分别求 最大值，然后将两个最大值相加，经多次比较，得到总的最大值。但是这会 出现一个问题，时间复杂度太大，为 。经测试，这种方式会导致Time Limited Exceed的错误。 那么现在需要考虑一下有没有可以改进的方法，答案是有的，可以利用一维 的动态规划来做，因为我们可以观察到，之前的方案之所以复杂度太大是因 为有很多重复的计算。而动态规划可以采取的方式是： 1）新开一个数组maxProfitWith，这个数组用来保存第i天可以获得的最大收 益。算法复杂度为 。 2）将prices数组都遍历一遍之后，可以知道最后一项，即 maxProfitWith[size-1]即为遍历一遍时的最大收益。 3）我们再逆序遍历一遍，计算当前i到最后一天的最大收益，与之前的0至第i 天的最大收益相加，可以得到总的最大收益finalProfit，比较之后，可以得到 最终结果，算法复杂度也是 。 4 ）最终的算法复杂度就是 。 class Solution { public: 1 int maxProfit(vectorint prices) { if(prices.empty()) return 0; int si e=prices.si e(); int lowest=prices[0]; vectorint maxProfitWith; maxProfitWith.push_back(0); int maxProfit=0; for(int i=1;isi e;i++) { int profit=prices[i]-lowest; if(profitmaxProfit) maxProfit=profit; maxProfitWith.push_back(maxProfit); if(prices[i]lowest) lowest=prices[i]; } int highest=prices[si e-1]; int finalProfit=maxProfitWith[si e-1]; maxProfit=0; for(int i=si e-2;i=0;i--) { int profit=highest-prices[i]; if(profitmaxProfit) maxProfit=profit; int maxSum=maxProfitWith[i]+maxProfit;