# 2 ms Java DP solution beats 99.87%

• The basic idea is similar to solution here: https://leetcode.com/discuss/75785/2ms-java-dp-solution

I generalized it to K transactions.

``````public class Solution {
public int maxProfit(int k, int[] prices) {
if (k <= 0 || prices == null || prices.length <= 0) return 0;
if (k > prices.length / 2) { // in this case, it's the same problem as Best Time to Buy & Sell Stock II
int max = 0;
for (int i = 0; i < prices.length - 1; i++) {
int diff = prices[i + 1] - prices[i];
max += diff>0 ? diff : 0;
}
return max;
} else {
int [] buy = new int[k];
int [] sell = new int[k];

for (int price: prices) {
int tmp = 0;
for (int i = 0; i < k; i ++) {
int buffer = 0;                          // used to avoid duplicate calculation
buffer = tmp - price;
if (buy[i] < buffer) buy[i] = buffer;

buffer = buy[i] + price;
if (sell[i] < buffer) sell[i] = buffer;
tmp = sell[i];
}
}

return sell[k - 1];
}

}
}``````

• Nice one..only thing I could not understand is that upper part when k>prices.length/2. To be accurate I think we still have to maintain track of how many transaction are done..Please explain this.

• I believe this part is because with more than prices.length / 2 transactions, it is the same as no transactions limit since you can do only 1 transaction per 2 days. Then it becomes the same problem as Best Time to Buy & Sell Stock II.

• Just test it and got " Time Limit Exceeded " but run more times it do reach 2 ms . cool
Mark for following readers .

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