714. Best Time to Buy and Sell Stock with Transaction Fee - cocoder39/coco39_LC GitHub Wiki

714. Best Time to Buy and Sell Stock with Transaction Fee

buy[i]: max profit if the last operation at i is buying sell[i]: max profit if the last operation at i is selling sell[0] = 0

can be compressed to O(1) sapce

public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }
        
        int buy[] = new int[len];
        int sell[] = new int[len];
        
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < len; i++) {
            sell[i] = Math.max(sell[i-1], buy[i-1] + prices[i] - fee);
            buy[i] = Math.max(buy[i-1], sell[i-1] - prices[i]);
        }
        return sell[len - 1];
    }