风口的猪（小米实习生招聘）

题目：

风口之下，猪都能飞。当今中国股市牛市，真可谓“错过等七年”。给你一个回顾历史的机会，已知一支股票连续n天的价格走势，以长度为n的整数数组表示，数组中第i个元素（prices[i]）代表该股票第i天的股价。

假设你一开始没有股票，但有至多两次买入1股而后卖出1股的机会，并且买入前一定要先保证手上没有股票。若两次交易机会都放弃，收益为0。设法计算你能获得的最大收益。输入数值范围：2<=n<=100，0<=prices[i]<=100

输入例子:

3,8,5,1,7,8

输出例子:

12

java版本的代码实现：

package cn.cat.test;


public class Test25 {

	public static void main(String[] args) throws ClassNotFoundException {
		//股票走势。随便列举一些数据。
		int[] prices = new int[]{3, 8, 5, 5, 7, 8};
		
		int maxValResult = Integer.MIN_VALUE;
		int[] segm01Result = null;
		int[] segm02Result = null;
		
		for (int i = prices.length - 1; i >= 0 ; i--) {
			for (int j = i - 1; j > 1; j--) {
				int[] segm02 = getMaxDifferVal(prices, j, i);
				int[] segm01 = getMaxDifferVal(prices, 0, j - 1);
				if (maxValResult < segm02[0] + segm01[0]) {
					maxValResult = segm01[0] + segm02[0];
					segm01Result = segm01;
					segm02Result = segm02;
				}
			}
		}
		
		
		System.out.println(String.format("最大差值为%d, 在第%d天买入，在第%d天卖出, 在第%d天买入，在第%d天卖出", 
				maxValResult, segm01Result[1] + 1, segm01Result[2] + 1,
				segm02Result[1] + 1, segm02Result[2] + 1));
		
	}
	//获取最大差值。元素1为差值，元素2为减数下标，元素3为被减数下标
	static int[] getMaxDifferVal(int[] prices, int startIndex, int endIndex) {
		int maxVal = Integer.MIN_VALUE;
		int iIndex = -1;
		int jIndex = -1;
		for (int i = endIndex ; i > startIndex; i--) {
			for (int j = i - 1; j >= startIndex; j--) {
				if (prices[i] - prices[j] > maxVal) {
					maxVal = prices[i] - prices[j];
					iIndex = i;
					jIndex = j;
				}
			}
		}
		return new int[]{maxVal, jIndex, iIndex};
	}
	

}