题解 | #最大差值# 动态规划

这题其实跟********121.买卖股票的最佳时机是一个题

每遍历一个数，保存遍历到的最小值，更新最大差值即可

#include <algorithm>
#include <climits>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A int整型vector
     * @param n int整型
     * @return int整型
     */
    int getDis(vector<int>& A, int n) {
        // write code here
        int maxDiff = 0, minNum = A[0];
        for (const int& x : A) {
            maxDiff = max(maxDiff, x - minNum);
            minNum = min(minNum, x);
        }
        return  maxDiff;
    }
};

时间复杂度：O(n)，遍历数组花费的时间

空间复杂度：O(1)