题目描述

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

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

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

样例

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

输出：11

算法

(买卖股票)

1. 重点就是 如何枚举，也就是枚举的顺序，这里枚举的是 在第几天卖出股票。
2. 使用一个变量来维护当前前i - 1天中买入股票的最小值，将时度从$O(n^2)$变成了$O(n)$。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& A) {
        if(A.empty() || A.size() == 1) return 0;

        int res = -2e9;
        int minv = A[0];
        for(int i = 1; i < A.size(); i ++)
        {
            minv = min(minv, A[i]);
            res = max(res, A[i] - minv);
        }

        return res;

    }
};