#include <vector>
#include <algorithm>

using std::vector;
using std::max;

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        // dp[i] means max profit at i with not stock
        // dp[i] = max(dp[i - 1], prices[i] + max(dp[j] - prices[j] - fee)), j in [0, i - 1]
        //                                     ╰-> tmp
        int dp = 0;
        if (prices.size() == 0) return dp;
        int tmp = -prices[0] - fee;
        for (int i = 1; i < prices.size(); i++) {
            dp = max(dp, prices[i] + tmp);
            tmp = max(tmp, dp - prices[i]- fee);
        }
        return dp;
    }
};

#include <cstdio>

int main() {
    Solution *sol = new Solution();

    vector<int> prices = {1, 3, 2, 8, 4, 9};
    int fee = 2;
    int ans = sol->maxProfit(prices, fee);
    printf("%d\n", ans);

    prices = {1, 1, 1, 1, 1, 1};
    fee = 1;
    ans = sol->maxProfit(prices, fee);
    printf("%d\n", ans);

    return 0;
}