Java code exceed time limit


  • 0
    Y
    public class Solution {
    public int maxProfit(int[] prices) {
        /*
        Bottom-up approach
        Profit(selldatelimit, buydatelimit) = max{Profit(selldate-1, buydate), Profit(selldate, buydate+1), p[selldate] - p[buydate]} this is the maximum profit we can get from the time range of buydatelimit to the selldatelimit
        Profit(selldatelimit, buydatelimit) = 0 if selldate = buydate
        Profit(selldatelimit, buydatelimit) doesn't exist if selldatelimit < buydatelimit
        i = selldatelimit
        j = buydatelimit
        i >= j
        */
        int l = prices.length;
        if (l == 0){
            return 0;
        }
        int[][] profit = new int[l][l];
        for (int c = 0; c <= l - 1; c++){
            for (int j = 0; j <= l - 1 - c; j++){
                int i = j + c;
                if (i == j){
                    profit[i][j] = 0; //buy and sell at the same day, profit is 0
                }
                else{
                    profit[i][j] = profit[i][j+1] > profit[i-1][j] ? profit[i][j+1] : profit[i-1][j];
                    profit[i][j] = profit[i][j] > (prices[i] - prices[j]) ? profit[i][j] : prices[i] - prices[j];
                    //profit[i][j] is the largest one among the three ones
                }
            }
        }
        
        return profit[l - 1][0]; //return the largest profit we can get from the time range of the first day to the last day
    }
    

    }

    My code seems to exceed time limit when it comes to a very large input set. Is it due to its O(n^2) time and O(n^2) space?
    I am a beginner so that's why I code it in dynamic program style without space optimization.
    Thank you for helping me.


  • 1
    C

    It exceeds due to the time complexity I think. There is a very big array with almost 25k elements which fails the brute force approach.


  • 0
    Y

    Thank you. That should be the problem.


Log in to reply
 

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