股票的最大利润

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖 一次 该股票可能获得的利润是多少？

例如一只股票在某些时间节点的价格为[9, 11, 8, 5, 7, 12, 16, 14]。

如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。

样例

输入：[9, 11, 8, 5, 7, 12, 16, 14]

输出：11

[HTML_REMOVED]

法一：思路比较清晰，很多人一开始就想到的是，从当前位置向前遍历，找到一个最小的数字，然后两个相减，就是当前位置能获得的最大利润，这样的话时间复杂度为O(n^2)。那么我们优化的方法就是使用打表，也就是动态规划，将最小值存在一个表中，然后一次遍历，直接相减即可。

public int maxDiff(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int len = nums.length;
    //minPrice[i]代表i之前的最小值
    int[] minPrice = new int[len];
    minPrice[0] = Integer.MAX_VALUE;
    for (int i = 1; i < len; i++) {
        minPrice[i] = Math.min(minPrice[i - 1], nums[i - 1]);
    }
    int ans = 0;
    for (int i = 1; i < len; i++) {
        ans = Math.max(ans, nums[i] - minPrice[i]);
    }
    return ans;
}