DP O(kn), time limit exceeded, while local test pass in 13ms


  • 0
    D

    I don't know why it happens.

    I used the way of DP in O(kn) complexity, and local test is OK, but online test time limit exceed.

    code is as follows :

    public int maxProfit(int k, int[] prices) {
    int len = prices.length;

        if (k > len) {
            k = len;
        }
    
        int[][] profit = new int[k][2];
        int[] buy = new int[k];
    
        if (k < 1 || len < 1) {
            return 0;
        }
    
        for (int i=0; i<k; i++) {
            profit[i][0] = 0;
            profit[i][1] = 0;
            buy[i] = prices[0];
        }
    
        for (int i=1; i<len; i++) {
            for (int j=1; j<k; j++) {
                profit[j][0] = Math.max(profit[j][0], profit[j-1][1] + prices[i] - buy[j]);
                if (profit[j][1] < profit[j-1][0]) {
                    profit[j][1] = profit[j-1][0];
                    buy[j] = prices[i];
                }
            }
        }
    
        return Math.max(profit[k-1][0], profit[k-1][1] + prices[len-1] - buy[k-1]);
    }

  • 0
    V

    When k>=len/2, the solution is equivalent to the unlimited version, so you can solve it in O(N) time. Hence you can optimize it in this case.


  • 0
    D

    Yeah, I didn't realize this before.
    But even in worst case, I don't think this solution will cause time limit exceed, quite strange.


  • 1
    D

    Ah...I suddenly understand.......

    As such kind of optimization exists. There will be data that are designed for this case, only O(n) can pass, O(kn) will fail.


  • 0
    E

    not exactly,when the K is quite larger than N,such as N^2, your solution is so bad.


Log in to reply
 

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