# Space O(N) Time O(N*K) DP and Not Checking K > prcies.Length / 2 at all

• Performance hurts a little bit when executing the hardest test case which is because the way of length/2 using O(n) made it faster while this solution is calculating using dp which is O(n * k)

``````public int MaxProfit(int k, int[] prices){
int[] dp = new int[prices.Length];
for(int i = 1, lastMax = 0; i <= k && i < prices.Length; i++){
for(int j = 1, increase = int.MinValue, lastProfit = dp[0]; j < prices.Length; j++){
int tmp = dp[j];
increase = Math.Max(increase, lastProfit - prices[j - 1]);
dp[j] = Math.Max(dp[j - 1], prices[j] + increase);
lastProfit = tmp;
}
if(lastMax == dp[prices.Length - 1]) break;
else lastMax = dp[prices.Length - 1];
}
return prices.Length == 0 ? 0 : dp[prices.Length - 1];
}
``````

Below is the original solution with k compare with length/2.

``````public int MaxProfit(int k, int[] prices){
if(k >= prices.Length / 2){
int result = 0;
for(int i = 1; i < prices.Length; i++)
result += prices[i] - prices[i - 1] <= 0 ? 0 : prices[i] - prices[i - 1];
return result;
}
int[] dp = new int[prices.Length];
for(int i = 1, lastMax = 0; i <= k; i++){
for(int j = 1, increase = int.MinValue, lastProfit = dp[0]; j < prices.Length; j++){
int tmp = dp[j];
increase = Math.Max(increase, lastProfit - prices[j - 1]);
dp[j] = Math.Max(dp[j - 1], prices[j] + increase);
lastProfit = tmp;
}
if(lastMax == dp[prices.Length - 1]) break;
else lastMax = dp[prices.Length - 1];
}
return dp[prices.Length - 1];
}``````

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