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).

原题链接：https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

题目：假设你有一个数组，其中的第 i 个元素代表给定的第 i 天的股票价格。

设计一个算法找出最大的利润。你可以完成最多两次交易。

思路：将数组分成前后两个区间，求出这两个区间的最大差值。

借鉴了网友的做法[1]。动态规划，用两个数组记录状态，f[i]表示区间[0,i](0<=i<=n-1) 的最大利润，g[i]表示区间[i,n-1](0<=i<=n-1) 的最大利润。

	public static int maxProfit(int[] prices) {
		if (prices.length < 2)
			return 0;
		int f[] = new int[prices.length];
		int g[] = new int[prices.length];
		for (int i = 1, valley = prices[0]; i < prices.length; ++i) {
			valley = Math.min(valley, prices[i]);
			f[i] = Math.max(f[i - 1], prices[i] - valley);
		}
		for (int i = prices.length - 2, peak = prices[prices.length - 1]; i >= 0; --i) {
			peak = Math.max(peak, prices[i]);
			g[i] = Math.max(g[i], peak - prices[i]);
		}
		int max_profit = 0;
		for (int i = 0; i < prices.length; ++i)
			max_profit = Math.max(max_profit, f[i] + g[i]);
		return max_profit;
	}