dp

121. 买卖股票的最佳时机 - 力扣（LeetCode）

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

超时

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

作者：relaxed-matsumotowq3
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solution/dong-tai-gui-hua-by-relaxed-matsumotowq3-zjxq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。