动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minval = INT_MAX;
        int res = 0;
        for (auto x : prices) {
            minval = min(minval, x);
            res = max(res, x - minval);
        }
        return res;
    }
};

April 14, 2024 2:19 AM (GMT+8) 自己做的时候用贪心写了出来

贪心的点在于可以试错

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