#include <iostream>#include <stdio.h>#include <vector>using namespace std;/*問題: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).分析:至少要交易兩次，求取至少交易兩次下的最大值。因為無法確定到底交易多少次。也有可能一直在虧損，那么就要選取虧損較少的時候。這個有點類似于廣度優先搜索求解最優，但這個是如果是暴力破解：沒辦法破解，因為至少兩次，至多只有n-1次，應該是一個動態規劃問題。設dp[i]表示截止到天數i獲得的最大利潤。B[i]表示最近一次拋售股票的日期，那么dp[i+1]要么是還等于dp[i]，記j=B[i],從j到天數i+1中選擇出一個兩天，組成一次交易并且有maxNum = 0;maxNum = max( A[i+1] - A[j] , maxNum )，其中j 屬于[ B[i] , i ]如果maxNum > 0,那么又選擇了j和i+1作為一次新的交易設計一個計數器cunt，每次組成新的交易，累加，目標是dp[n]，先計算第一遍，求出dp[n]，如果count = 0，說明沒有選擇交易，說明整個是降序的，那么遍歷一遍，選擇兩次：兩個差值最大的(實際比如9 7,和9 4,兩個查實分別為-2，-5，應該選擇-2)如果count = 1,說明還缺少一次交易，則根據之前一次記錄的交易截止天數i，從i到n開始都是降序，那么就尋找兩個差值最大的如果count >= 2，直接返回結果似乎還是不對。看答案:leecode:https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/?tab=Solutions需要維護一個通過k次交易，到達prices[i]時候的最大利潤，也就是記錄了：交易次數，交易截止日期i,以及最大利潤三個變量【關鍵】我沒想到是記錄交易次數，但題目說了交易次數，就應該把其抽象為要記錄的變量設dp[k][i]表示截止到prices[i]，通過k次交易，所能得到的最大利潤，不包括第prices[i]，八這個變量需要留作下一次使用第k次得到最大利潤，等于截止到日期j，通過k-1次得到最大的利潤，加上prices[j] - prices[i]的利潤 和 不需要包含當前這個元素的利潤dp[k-1][i-1]的最大值中的其中一個，漏了dp[k][i]= max(dp[k][i-1], dp[k-1][j] + prices[i] - prices[j] ),其中j屬于[]dp[0][i] = 0，表明通過0次想要賺得的最大利潤為0dp[k][0]= 0,表明如果僅有一個價格prices[0]，那么獲得的最大利潤為02//dp[0][i] = 0//dp[k][0] = 0，所以無需再初始化//dp[k][i] = max( dp[k][i-1] , dp[k-1][j] + prices[i] - prices[j] ),j屬于[0 , i-1]//         = max ( dp[k][i-1], prices[i] + max(dp[k-1][j] - prices[j]),牛逼，把常量全部提取出來//目標值dp[2][n-1]int maxProf = 0;for(int k = 1 ; k <= K ; k++)//這里限定k的結果,必須從1開始因為后面有k-1{	int tempMax = dp.at(k-1).at(0) - prices.at(0);	for(int i = 1; i < size ; i++)//下標從1開始	{		dp.at(k).at(i) = max( dp.at(k).at(i-1) , prices.at(i) + tempMax );		//牛逼把常量拆分出來，最大值通過一次遍歷即可，無需再次開一個循環		tempMax = max(tempMax , dp.at(k-1).at(i) - prices.at(i));		maxProf = max(maxProf, dp.at(k).at(i));	}}*/class Solution {public:    int maxProfit(vector<int>& prices) {        if(prices.empty())		{			return 0;		}		//只有1個價格，無法交易		if(prices.size() <= 1)		{			return 0;		}		int size = prices.size();		int K = 2;		vector< vector<int> > dp( K + 1, vector<int>(size , 0) );		//dp[0][i] = 0		//dp[k][0] = 0，所以無需再初始化		//dp[k][i] = max( dp[k][i-1] , dp[k-1][j] + prices[i] - prices[j] ),j屬于[0 , i-1]		//         = max ( dp[k][i-1], prices[i] + max(dp[k-1][j] - prices[j]),牛逼，把常量全部提取出來		//目標值dp[2][n-1]		int maxProf = 0;		for(int k = 1 ; k <= K ; k++)//這里限定k的結果,必須從1開始因為后面有k-1		{			int tempMax = dp.at(k-1).at(0) - prices.at(0);			for(int i = 1; i < size ; i++)//下標從1開始			{				dp.at(k).at(i) = max( dp.at(k).at(i-1) , prices.at(i) + tempMax );				//牛逼把常量拆分出來，最大值通過一次遍歷即可，無需再次開一個循環				tempMax = max(tempMax , dp.at(k-1).at(i) - prices.at(i));				maxProf = max(maxProf, dp.at(k).at(i));			}		}		return maxProf;	}};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}