not best time, But easy recursion way in JAVA


  • 0
    T
    public class Solution {
    
        private int[] buy;
        private int[] noBuy;
    
        public int maxProfit(int[] prices) {
            buy = new int[prices.length];
            noBuy = new int[prices.length];
            Arrays.fill(buy, Integer.MIN_VALUE);
            Arrays.fill(noBuy, Integer.MIN_VALUE);
            return maxProfit(prices, 0, false);
        }
    
    
        private int maxProfit(int[] prices, int i, boolean isBuy) {
    
            if (i >= prices.length) {
                return 0;
            }
            if (isBuy) {
                if (buy[i] != Integer.MIN_VALUE)
                    return buy[i];
                return buy[i] = Integer.max(maxProfit(prices, i + 1, true), prices[i] + maxProfit(prices, i + 2, false));
            } else {
                if (noBuy[i] != Integer.MIN_VALUE)
                    return noBuy[i];
                return noBuy[i]= Integer.max(maxProfit(prices, i + 1, false), maxProfit(prices, i + 1, true) - prices[i]);
            }
        }
    
        public static void main(String[] args) {
            System.out.println(new Solution().maxProfit(new int[]{1, 2, 3, 0, 2}));
        }
    }
    

Log in to reply
 

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