题目描述

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

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

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

样例

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

输出：11

算法

(模拟) $O(n)$

用一个变量 minv 存储前 i - 1 天股票的最低价格，即最合适的买入时期，res 记录最大利润
遍历整个数组每次计算利润，更新 minv 和 res

时间复杂度

遍历一遍数组，时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if (nums.empty()) return 0;

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