【LeetCode教你买股票】买卖股票的最佳时机

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0, m = 1e4 + 1;
        for (auto e : prices)
        {
            m = min(m, e);
            res = max(res, e - m);
        }   
        return res;
    }
};

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

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

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        const int N = 0x3f3f3f3f;
        vector<int> f(3, -N);
        auto g = f;
        f[0] = -prices[0];
        g[0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                f[j] = max(f[j], g[j] - prices[i]);
                if (j > 0) g[j] = max(g[j], f[j - 1] + prices[i]);
            }
        }
        int res = 0;
        for (auto e : g) 
        {
            res = max(res, e);
        }
        return res;
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        const int N = 0x3f3f3f3f;
        vector<int> f(k + 1, -N);
        auto g = f;
        f[0] = -prices[0];
        g[0] = 0;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j <= k; j++)
            {
                f[j] = max(f[j], g[j] - prices[i]);
                if (j > 0) g[j] = max(g[j], f[j - 1] + prices[i]);
            }
        }
        int res = 0;
        for (auto e : g) res = max(res, e);
        return res;
    }
};

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

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