static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int high, low, max_diff, prev, current;
        int len = prices.size();
        int result = 0;
        vector<vector<int>> dp(2, vector<int>(len+1, 0));
        if(len == 0) return result;
        if(k > len/2) {
            low = prices[0];
            for(int i = 1; i < len; ++i) {
                if(prices[i] < prices[i-1]) {
                    result += prices[i-1]-low;
                    low = prices[i];
                }
            }
            result += prices[len-1] - low;
        } else {
            for(int i = 1; i <= k; ++i) {
                current = i & 1;
                prev = current ^ 1;
                for(int j = 0; j < len; ++j) {
                    low = high = prices[j];
                    max_diff = 0;
                    dp[current][j] = 0;
                    for(int g = j+1; g < len; ++g) {
                        dp[current][j] = max(dp[current][j], dp[prev][g]+max_diff);
                        high = max(high, prices[g]);
                        if(prices[g] < low) low = high = prices[g];
                        max_diff = max(max_diff, high-low);
                    }
                    dp[current][j] = max(dp[current][j], max_diff);
                    result = max(result, dp[current][j]);
                }
            }
        }
        return result;
    }
};