分享程序员开发的那些事...
更新时间：2022-08-25 17:26:30
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).
题解： 参考http://www.cnblogs.com/springfor/p/3877068.html
根据题目要求，最多进行两次买卖股票，而且手中不能有2只股票，就是不能连续两次买入操作。
所以，两次交易必须是分布在2各区间内，也就是动作为：买入卖出，买入卖出。
进而，我们可以划分为2个区间[0,i]和[i,len-1]，i可以取0~len-1。
那么两次买卖的最大利润为：在两个区间的最大利益和的最大利润。
一次划分的最大利益为：Profit[i] = MaxProfit(区间[0,i]) + MaxProfit(区间[i,len-1]);
最终的最大利润为：MaxProfit(Profit[0], Profit[1], Profit[2], ... , Profit[len-1])。
C++实现代码：
#include<iostream> #include<vector> using namespace std; class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int n=prices.size(); int i; int low=prices[0]; int left[n]; left[0]=0; for(i=1;i<n;i++) { low=min(low,prices[i-1]); left[i]=max(left[i-1],prices[i]-low); } int high=prices[n-1]; int right[n]; right[n-1]=0; for(i=n-2;i>=0;i--) { high=max(high,prices[i+1]); right[i]=max(right[i+1],high-prices[i]); } int maxSum=0; for(i=0;i<n;i++) { maxSum=max(maxSum,left[i]+right[i]); } return maxSum; } }; int main() { Solution s; vector<int> vec={1,4,6,8,3,5,9,3,6}; cout<<s.maxProfit(vec)<<endl; }