计算股票最大收益

       给定一个整数数组，数组的值代表股票的历史价格，找出令收益最大的买点和卖点。

       类似于找出数组中的最大差值，不过多了一个限定条件，就是买点必须在卖点之前。下面是用java写的一个时间复杂度为O(n)的算法。

public class TestStock {
	public static void main(String[] args) {
		int[] prices = { 32, 69, 3, 8, 1, 2, 19, 22, 2, 35, 23 };
		// int[] prices = { 35, 23, 22, 18, 15, 13, 1 };
		int[] result = maxProfit(prices);
		System.out.println("买入价为" + result[0] + "，卖出价为" + result[1] + "，利润为"
				+ result[2] + "。");
	}

	public static int[] maxProfit(int[] prices) {
		if (prices.length < 2) {
			throw new RuntimeException("股票价格数不小于2");
		}
		int lowPoint = prices[0];// 买入点
		int maybeLowPoint = prices[0];// 可能的买入点
		int hignPoint = prices[1];// 卖出点
		int diff = prices[1] - prices[0];// 差价
		for (int i = 1; i < prices.length; i++) {
			if (prices[i] < maybeLowPoint) {
				// 如果价格一直跌，选择跌得最少的那个点买入卖出
				if (prices[i] - maybeLowPoint > diff) {
					diff = prices[i] - maybeLowPoint;
					lowPoint = maybeLowPoint;
					hignPoint = prices[i];
				}
				maybeLowPoint = prices[i];
			} else {
				if (prices[i] - lowPoint > diff) {
					diff = prices[i] - lowPoint;
					hignPoint = prices[i];
				}
				if (prices[i] - maybeLowPoint > diff) {
					diff = prices[i] - maybeLowPoint;
					lowPoint = maybeLowPoint;
					hignPoint = prices[i];
				}
			}
		}
		// 将结果返回
		int[] result = new int[3];
		result[0] = lowPoint;
		result[1] = hignPoint;
		result[2] = diff;
		return result;
	}
}

       首先假设数组第一个数为买入点，第二个数为卖出点，第二个数减去第一个数为最大利润。问题的关键是什么时候替换买入点和卖出点。这里需要引入另一个常量，初始值与买入点相同，记作备用买入点。接着就可以开始遍历数组了。如果当前值比买入点还要低，我们先将这个值赋给备用买入点，因为不能保证后面还有值与其相减会大于原先的最大利润。如果当前值减去备用买入点大于原先的最大利润，将这个值赋给卖出点，将备用买入点赋给买入点，同时更新最大利润。

       当最大利润不为正数，即数组里的数是递减的时候，需要在赋值给备用买入点之前再加一个判断。如果当前值减去备用买入点大于最大利润，更新买入点，卖出点及最大利润。