C++ backtracking got TLE


  • 0
    class Solution {
    public:
        int findNumberOfLIS(vector<int>& nums) {
            if(nums.empty()) return 0;
            unordered_map<int, int>m;
            int maxlen = 1;
            for(int i = 0; i < nums.size(); i++)
                DFS(nums, i, m, 1, maxlen);
            return m[maxlen];
        }
    
        void DFS(vector<int>& nums, int k, unordered_map<int, int>& m, int len, int& maxlen){
            maxlen = max(maxlen, len);
            if(len == maxlen) m[len]++;
            for(int i = k + 1; i < nums.size(); i++)
                if(nums[i] > nums[k]) DFS(nums, i, m, len + 1, maxlen);
        }
    };
    

Log in to reply
 

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