Java Clean Two State DP Solution O(N)


  • 1
    S

    buy[i] stands for Max profit we can get end with buy till price[i];
    sell[i] stands for Max profit we can get end with Sell till price[i];

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

  • 0

    @SPARC Your name reminds me of a company.


Log in to reply
 

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