121. 买卖股票的最佳时机

区间内，差值最大，注意并不是最低值和最大值差值就是最大，例如，3，7，1，3，4。差值最大是7-3

解法一: 暴力计算

遍历所有可能性，记录最大值

空间复杂度：O(n)
时间复杂度：O(n^2)

显然这个时间复杂度是不可接受

public int maxProfit(int[] prices) {
 if (prices == null || prices.length <= 1)
 return 0;
 int n = prices.length;
 int max = 0;
 for (int i = 0; i < n; i++) {
 for (int k = i + 1; k < n; k++) {
 int diff = prices[k] - prices[i];
 if (diff > 0 && diff > max)
 max = diff;
 }
 }
 return max;
}

解法二

股票低买高卖，

假设第一天买进，后面天数买进/卖出

1. 假设买进，价格更低，假设买进min更新当前最少值
2. 假设卖出
   1. 当前卖出利润更大，更新最大利润（此时最大利润当前价格 - 之前价格最低点）
   2. 当前卖出利润更新，则不更新

public int maxProfit(int[] prices) {
 if (prices == null || prices.length <= 1)
 return 0;
 int min = prices[0], max = 0;
 for (int i = 1; i < prices.length; i++) {
 if (prices[i] < min) {
 min = prices[i];
 } else if (prices[i] - min > max) {
 max = prices[i] - min;
 }
 }
 return max;
}