Trying a recursive approach with memoization, getting TLE


  • 0
    S

    Using the following java code :

    public class Solution {
        int[][] memoize = new int[1000001][2];
        public int maxProfit(int[] prices) {
            for(int i =0;i<1000001;i++){
                for(int j=0;j<2;j++){
                    memoize[i][j] = -1;
                }
            }
            return func(prices, 0, 0);
        }
        
        public int func(int[] prices, int index, int signal){
            int ans = 0;
            if(index >= prices.length){
                return ans;
            }
            if(memoize[index][signal] != -1){
                return memoize[index][signal];
            }
            if(signal == 0){
                ans = Math.max(func(prices, index+1, 1) - prices[index], func(prices, index+1, 0));
            }else{
                ans = Math.max(func(prices, index+2, 0) + prices[index], func(prices, index+1, 1));
            }
            memoize[index][signal] = ans;
            return ans;
        }
    }
    

    Idea is that at each point either buy or sell or no_action will happen. Buy and sell will be specified by parameter signal and no_action can be at any time(cool_off is also no_action).

    So,
    dp[i, sell] = max(dp[i+1, sell], dp[i+2, buy] + price[i])

    dp[i, buy] = max(dp[i+1, sell] - price[i], dp[i+1, buy]])

    With memoization, this code should pass through each_day and action(sell or buy) at max once. So, the time complexity should be O(n).

    Please suggest, where this is going wrong and taking long time, it is timing out for a small test case like [4,1,2].

    Also please correct where I am making mistake, not able to figure out.


Log in to reply
 

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