股票的最大利润

题目：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少? 例如，一只股票在某些时间节点的价格为 $[9, 11, 8, 5, 7, 12, 16, 14]$。如果我们能在价格为 $5$ 的时候买入并在价格为 $16$ 时卖出，则能收获最大的利润 $11$。

如果我们使用蛮力法来解决这个问题，在访问数组中的数字时买入，然后寻找后面的最大值卖出，得到买卖的差值，而我们使用变量保存最大的买卖差值，这样的算法的时间复杂度为 $O(n^2)$。

如果我们换一种思路，如果我们以 $diff(i)$ 表示以数组中第 $i$ 数字将股票卖出能够获得的最大利润($i$ 从 $0$ 开始)，在卖出的价格一定时，买入的价格越低越好，所以我们只要找出前面 $i-1$ 个数字中的最小值即可得到买卖的最大利润，但是我们不用扫描前面的数字，我们完全可以使用一个变量将前面的最小值记录下来。所以这样做的时间复杂度为 $O(n)$，我们只需要扫描一遍数组即可。

代码如下

public static int maxDiff(int[] data) {
    if (data == null || data.length <= 1) {
        return 0;
    }
    // 最大差值
    int maxDiff = 0;
    int min = data[0];
    for (int i = 2; i < data.length; i++) {
        if (data[i] > min) {
            // 计算以 data[i] 卖出时的最大差值
            int diff = data[i] - min;
            if (diff > maxDiff) {
                maxDiff = diff;
            }
        } else {
            // 更新最小值
            min = data[i];
        }
    }
    return maxDiff;
}