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。
2.说明
输入说明：
首先输入prices数组元素数目n，然后输入n个整数
输出说明：
输出一个整数
3.范例
输入：
8
3 3 5 0 0 3 1 4
输出：
6
4.思路
相比于买卖股票的最佳时机1和2，本题增加了交易次数的限制，智能交易两次，因此无法使用贪心算法。
本题思路和买卖股票的最佳时机1差不多，只是增加了1次的交易，因此有两种交易状态，buy1、buy2、sell1、sell2，其状态转移方程：
buy1 = max(buy1 , 0 - prices[i])
sell1 = max(sell1 , buy1 + princes[i])
buy2 = max(buy2 , sell1 - prices[i])
sell2 = max(sell2 , buy2 + prices[i])
边界问题：第一次交易，buy1=-prices[0]，sell1=0，相当于当天买当天卖；第二次交易，buy2=sell1 - prices[0]，sell2=0，相当于和第一次交易在同一天，也是第一次交易后买入和卖出，最后返回sell2即为最终总收益。
5.代码
#include <iostream> #include <vector> #include <stdio.h> #include <algorithm> using namespace std; class Solution { public: int maxProfit(vector<int> &prices) { if(prices.size()==0) return 0; int buy1=-prices[0]; int sell1=0; int buy2=-prices[0]; int sell2=0; for(int i=1;i<prices.size();i++) { buy1=max(buy1,-prices[i]); sell1=max(sell1,buy1+prices[i]); buy2=max(buy2,sell1-prices[i]); sell2=max(sell2,buy2+prices[i]); } return sell2; } }; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n; cin>>n; vector<int> prices; int data; for(int i=0;i<n;i++) { cin>>data; prices.push_back(data); } int res=Solution().maxProfit(prices); cout<<res<<endl; return 0; }