算法1

(遍历) $O(n)$

由于只允许做一次股票买卖交易，枚举每一天作为卖出的日子，买入日子一定在卖出日子之前，为了获利最多，希望买入的日子的股票价格尽可能低。用minnum[i]记录第0-i天的最低价格，则在第i天卖出的最大获利为nums[i]-minnum[i]，枚举i找到最大获利。

时间复杂度分析：$O(n)$

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size()==0)
            return 0;
        vector<int>minnum(nums.size(),0);
        minnum[0] = nums[0];
        for(int i = 1; i<nums.size(); i++){
            if(nums[i]<minnum[i-1])
                minnum[i] = nums[i];
            else
                minnum[i] = minnum[i-1];
        }
        int res = 0;
        for(int i = 0;i<nums.size();i++){
            int delta = nums[i] - minnum[i];
            if(delta > res)
                res = delta;
        }
        return res;
    }
};