Java backtrack, o(n) and space o(1)


  • 0
    N

    The solution here is similar to this straightforward solution.
    The only twist is to reverse the interaction order, which makes the initial settings easier.

    class Solution {
        public int maxProfit(int[] prices, int fee) {
            int profit = 0;    // best profit till now
            int opt = 0;      //  largest value of <profit before current> + <current price>
            for (int i=prices.length-1; i>=0; i--) {
                int temp = profit;
                profit = Math.max(opt - prices[i] - fee, profit);
                opt = Math.max(temp + prices[i], opt);
            }
            return profit;
            
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.