首页 > 代码库 > Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock III
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 before you buy again).
思路：使用动态规划的思想：分别从前往后和从后往前遍历数组，找出A[0]-A[i]和A[i]-A[n]区间内的最大利润。然后，再次遍历数组便能找出前一部分利润和后一部分利润加和最大的利润值。时间复杂度为O(n)。
1 class Solution { 2 public: 3 int maxProfit( vector<int> &prices ) { 4 int size = prices.size(); 5 if( size <= 1 ) { return 0; } 6 vector<int> invMaxProfit( size, 0 ); 7 int curMax = prices[size-1]; 8 for( int i = size-2; i >= 0; --i ) { 9 if( curMax <= prices[i] ) {10 curMax = prices[i];11 } else {12 invMaxProfit[i] = curMax - prices[i];13 }14 }15 int curMin = prices[0], profit = 0, totalProfit = invMaxProfit[0];16 for( int i = 0; i < size-1; ++i ) {17 if( curMin > prices[i] ) { curMin = prices[i]; }18 if( profit < prices[i] - curMin ) { profit = prices[i] - curMin; }19 if( totalProfit < profit + invMaxProfit[i+1] ) { totalProfit = profit + invMaxProfit[i+1]; }20 }21 return totalProfit;22 }23 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。