The time limitation of this problem is not reasonable


  • 1
    L

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

  • 0
    M

    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


Log in to reply
 

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