假设某股票的价格按照时间先后顺序存储在数组中，问买卖该股票一次可能获得的最大利润是多少？
- 如一支股票在某段时间内的价格为{9, 11, 8, 5, 7, 12, 16, 14}那么能在价格为5的时候购入并在价格为16时卖出，能获得最大利润11
转换成求每个位置价格和之前的最小股价的最大差问题，遍历每个位置，求出每个位置与之前位置的最大差，并记录下最大差，每次循环还保证记录下之前的最小值。
/**
* 扫描数组一次，时间复杂度为O(n)
* 遍历数组，同时记录当前数值和前面所有数值的最小值，计算并记录最大差值
* @param prices
* @return
*/
public int getMaxDiff(int[] prices) {
if (prices == null || prices.length < 0){
return 0;
}
//最大差值和前面的最小值
int maxDiff = 0;
int min = prices[0];
for (int i=1;i<prices.length;i++){
if (prices[i-1] < min) min = prices[i-1];
int diff = prices[i]-min;
if (maxDiff < diff) maxDiff = diff;
}
return maxDiff;
}
public static void main(String[] args) {
int[] prices = {9, 11, 8, 5, 7, 12, 16, 14};
MaxDiff maxDiff = new MaxDiff();
System.out.println(maxDiff.getMaxDiff(prices));
}
