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];
}
};
```