题目描述

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

样例

Example 1:

输入: [9, 11, 8, 5, 7, 12, 16, 14]
输出: 11
解释：如果我们能在价格为5的时候买入并在价格为16时卖出，则能收获最大的利润11。

算法1

(贪心) $O(n)$

思想同cornercao:

由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。

解法：

用buy记录当前最低的买入价格，用diff记录当前最大利润，遍历更新这两项。

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int buy=nums[0],diff=0;
        for(auto &x:nums){
            if(x<buy) buy=x;
            if(x-buy>diff) diff=x-buy;
        }
        return diff;
    }
};