# The time limitation of this problem is not reasonable

• Do optimisation when `k >= n / 2` is good, however considering the worst case when `k == n / 2 - 1`, the time complexity is still `O(N^2)`. So programs have `O(N^2)` complexity should get accepted.

But my program below which has this complexity got TLE. I think the time limitation and/or the test cases are not very reasonable for this problem.

``````class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.empty()) {
return 0;
}
int n = prices.size();
k = min(k, n / 2);
vector<int> f[2] = {vector<int>(n, 0), vector<int>(n, 0)};
for (int i = 1, i2 = 1; i2 <= k; i = 1 - i, i2++) {
f[i][0] = 0;
for (int j = 1, mx = -prices[0]; j < n; j++) {
int &x = f[i][j];
x = max(f[1 - i][j], f[i][j - 1]);
x = max(x, prices[j] + mx);
mx = max(mx, f[1 - i][j - 1] - prices[j]);
}
}
return f[k & 1][n - 1];
}
};``````

• Be careful about using std::max, which is quite slow. If time constraint is tight, you should you a macro instead :
#define Max(a,b) a > b ? a : b

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