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

• 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];

if (k < 1 || len < 1) {
return 0;
}

for (int i=0; i<k; i++) {
profit[i][0] = 0;
profit[i][1] = 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];
}
}
}

return Math.max(profit[k-1][0], profit[k-1][1] + prices[len-1] - buy[k-1]);
}``````

• 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.

• 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.

• 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.

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

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