188. Best Time to Buy and Sell Stock IV

dp II跟III的结合版

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        if (k > n / 2) { // 当k超过天数一半则不存在k个交易such that所有交易都不相邻，所以任意多个不相邻的交易的总数都不会超过k个
            int res = 0;
            for (int i = 1; i < n; ++i) {
                res += max(prices[i] - prices[i - 1], 0);
            }
            return res;
        }
        int m = 2 * k + 1;
        vector<vector<int>> f(n, vector<int>(m));
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int diff = prices[i] - prices[i - 1];
                if (j & 1) {
                    f[i][j] = max(f[i - 1][j] + diff, f[i - 1][j - 1]);
                } else {
                    f[i][j] = max(f[i - 1][j], j > 0 ? f[i - 1][j - 1] + diff : 0);
                }
            }
        }
        return *max_element(f[n - 1].begin(), f[n - 1].end());
    }
};

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        if (k > n / 2) {
            int res = 0;
            for (int i = 1; i < n; ++i) {
                res += max(prices[i] - prices[i - 1], 0);
            }
            return res;
        }
        int m = 2 * k + 1;
        vector<int> f(m);
        for (int i = 1; i < n; ++i) {
            for (int j = m - 1; j >= 0; --j) {
                int diff = prices[i] - prices[i - 1];
                if (j & 1) {
                    f[j] = max(f[j] + diff, f[j - 1]);
                } else {
                    f[j] = max(f[j], j > 0 ? f[j - 1] + diff : 0);
                }
            }
        }
        return *max_element(begin(f), end(f));
    }
};