last minute still TLE, should be OK, pity....


  • 0
    0
    class Solution {
    public:
        int removeBoxes(const vector<int>& boxes) {
            vector<int> used(boxes.size(), 1);
            return helper(boxes, used);
        }
    
        int helper(const vector<int>& b, vector<int>& u) {
            int result = 0;
            int p = cont(b, 0, u).first;
            while (p < (int)b.size()) {
                auto c = cont(b, p, u);
                int v = 0;
                for (int i = c.first; i < c.second; ++i) {
                    if (u[i] > 0) v++;
                    --u[i];
                };
                result = max(result, v * v + helper(b, u));
                for (int i = c.first; i < c.second; ++i) ++u[i];
                p = c.second;
            }
            return result;
        }
    
        pair<int, int> cont(const vector<int>& b, int s, vector<int>& u) {
            while (s < (int)b.size() && u[s] < 1) ++s;
            pair<int, int> ret {s, s};
            while (ret.second < (int)b.size() && (u[ret.second] < 1 || b[ret.second] == b[ret.first])) ++ret.second;
            return ret;
        }
    
    };

  • 0

    It should not be Okay. It's a brutal force without any optimization.


Log in to reply
 

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