Easy Java DP solution with O(n) time complexity and O(1) space complexity


  • 0
    P
        public int maxProfit(int[] prices, int fee) {
            int len =prices.length;
            int pbuy =-prices[0], cbuy=0 ;
            int psell=0, csell;
            for(int i=0; i<len; i++)
            {
                //if buy or not buy
                cbuy= Math.max(psell-prices[i],pbuy); // cbuy: the max profit prior to and at day i with last transaction ends at buy
                //if sell or not sell
                csell=Math.max(pbuy+prices[i]-fee,psell);//csell: the max profit prior to and at day i with last transaction ends at sell
                pbuy=cbuy;
                psell=csell;
            }
            
            return psell;
            
        }
    

Log in to reply
 

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