Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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).

int fun(vector<int> &prices){	int n = prices.size();	int profit1[n];	int profit2[n];	memset(profit1, 0, sizeof(profit1));	memset(profit2, 0, sizeof(profit2));	int leftMin = prices[0];	int rightMax = prices[n-1];	for (int i = 1; i < n; i++)	{		profit1[i] = max(profit1[i-1], prices[i]-leftMin);		leftMin = min(leftMin, prices[i]);	}	for (int i = n-2; i >= 0; i--)	{		profit2[i] = max(profit2[i+1], rightMax-prices[i]);		rightMax = max(rightMax, prices[i]);	}	int result = 0;	for (int i = 0; i < n; i++)	{		int temp = profit1[i] + profit2[i];		result = max(result, temp);	}	return result;}