本文主要是介绍Leetcode 123 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 (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
中文：
给你一堆数，表示股票，你现在最多有两次机会，可以将股票买进，然后卖出。得到的利润就是你卖出去的价格减去你买进的价格。
想要买股票，必须要先把手头的股票卖掉，而且只能按照数字的出现顺序来买。
问你最后最大利润能够为多少？
代码：
class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()<=1)return 0;int* stock1=new int[prices.size()+1];int* stock2=new int[prices.size()+1];memset(stock1,0,sizeof(int)*(prices.size()+1));memset(stock2,0,sizeof(int)*(prices.size()+1));stock1[0]=0;int mi=prices.front();for(int i=1;i<prices.size();i++){stock1[i]=max(stock1[i-1],prices[i]-mi);mi=min(mi,prices[i]);}stock2[prices.size()-1]=0;int mx=prices.back();for(int i=prices.size()-2;i>=0;i--){stock2[i]=max(stock2[i+1],mx-prices[i]);mx=max(mx,prices[i]);}int ans=stock2[0];for(int i=0;i<prices.size()-1;i++)ans=max(ans,stock1[i]+stock2[i+1]);delete [] stock1;delete [] stock2;return ans;}
};
解答：
由于最多只有两次买卖的机会，可以把这个数字序列分为两段，假设有n个数。
例如，从第i个数字开始分。
那么前i个数字买卖股票赚到的最大利润，加上第i+1到n数买卖股票得到的最大利润，就是最终结果。
设stock1[i]表示前i个数买卖的最大利润，实际上就是在前i个数当中找到两个数a和b的差值最大，而且b的下标大于a的下标。
如此，可以设置mi为枚举到前i-1个数是的最小数字，当枚举到第i个数prices[i]时，则使stock1[i]取stock1[i-1]与prices[i]-mi中较大的值，同时判断prices[i]与mi的大小关系，并更新mi。
同理，stock2[i]表示第i个数到第n个数之间进行一次买卖的最大利润，计算方法与stock1一样。
这篇关于Leetcode 123 Best Time to Buy and Sell Stock III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
