LeetCode 714.

package lc_714;

public class Solution {
    public int maxProfit(int[] prices, int fee) {
        int len = prices.length;
        int[] hold = new int[len];
        int[] not_hold = new int[len];

        hold[0] = -prices[0]-fee;
        int hold_max = Integer.MIN_VALUE;
        int not_hold_max = Integer.MIN_VALUE;
        int ans = Integer.MIN_VALUE;

        int last_hold_max = Integer.MIN_VALUE;
        int last_not_hold_max = Integer.MIN_VALUE;

        for (int i=1; i<len; i++){
            last_hold_max = Math.max(last_hold_max, hold[i-1]);
            last_not_hold_max = Math.max(last_not_hold_max, not_hold[i-1]);
            hold_max = Math.max(hold_max, last_not_hold_max);
            not_hold_max = Math.max(not_hold_max, last_hold_max);
            hold[i] = hold_max - prices[i] - fee;
            not_hold[i] = not_hold_max + prices[i];
            ans = Math.max(ans, not_hold[i]);
        }
        return Math.max(ans, 0);
    }

//    public int maxProfit(int[] prices, int fee) {
//        int len = prices.length;
//        int[] hold = new int[len];
//        int[] not_hold = new int[len];
//
//        hold[0] = -prices[0]-fee;
//        int hold_max = Integer.MIN_VALUE;
//        int not_hold_max = Integer.MIN_VALUE;
//        int ans = Integer.MIN_VALUE;
//
//        for (int i=1; i<len; i++){
//            for (int j=i; j>0; j--){
//                hold_max = Math.max(hold_max, not_hold[j-1]);
//                not_hold_max = Math.max(not_hold_max, hold[j-1]);
//            }
//            hold[i] = hold_max - prices[i] - fee;
//            not_hold[i] = not_hold_max + prices[i];
//            ans = Math.max(ans, not_hold[i]);
//        }
//        return Math.max(ans, 0);
//    }
}