题目描述

dp正常解法，和优化思路

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

dp[i]，表示在第i天卖股票能获得最大利润，买入时间可以为1~i-1种情况。
所以dp[i] =nums[i]- min(dp[1~i-1]),时间是O(n2),

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int maxDiff(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        int res=0;
        for(int i= 2;i<=n;i++)
        {
            for(int j=1;j<i;j++)
            {
                dp[i] = max(dp[i],nums[i-1]-nums[j-1]);
            }
            res = max(dp[i],res);
        }
        return res;
    }
};

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

其实上面是可以优化的，可以直接用一个变量记录前i天最低价格，一个变量记录当前结果。
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        int minux = nums[0];
        int res=0;
        for(int i= 2;i<=n;i++)
        {
            if(nums[i-1] <minux) minux = nums[i-1];
            res = max(nums[i-1]-minux,res);
        }
        return res;
    }
};