学习日记（C++、动态规划）

1、121买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=(int)prices.size(),ans=0;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                ans=max(ans,prices[j]-prices[i]);
            }
        }
        return ans;
    }
};

直接遍历的方法不可取，会超出时间限制，因为时间复杂度是o(n²)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i]表示从0到i比prices[i]小的最小值
        vector<int>dp(prices.size());
        dp[0]=prices[0];
        for(int i=1;i<prices.size();++i)
        {
            dp[i]=min(dp[i-1],prices[i]);
        }
        //最后用prices[i]-dp[i]，即为差最大
        
        int res=0;
        for(int i=0;i<prices.size();++i)
        {
            res=max(prices[i]-dp[i],res);
        }
        return res;
    }
};