What is the complexity of the graph traversal solution?


  • 0
    K

    I wonder what is the complexity of the graph traversal with memorisation solution. We say that there is an edge if (ai < aj && i < j). In this case, we just need to find the length of the longest path in this graph. So I just traverse and memorise the longest path from the current vertex to the end of the path. It seems to me that the complexity should be linear because we visit every vertex one time (due to memorisation) but this solution works slowly so I guess that I'm wrong.

        //graph traversal
        int f(int i, vector<int>& nums, vector<int>& mem) {
            if (i >= nums.size()) return 0;
            if (mem[i] != -1)
                return mem[i];
            mem[i] = 0;
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[j] > nums[i]) {
                    mem[i] = max(mem[i], f(j, nums, mem) + 1);
                }
                else
                    f(j, nums, mem);
            }
        
            return mem[i];
        }
        
        int lengthOfLIS(vector<int>& nums) {
            if (nums.size() == 0)
                return 0;
            vector<int> mem(nums.size(), -1);
            int res = 0;
            for (int i = 0; i < nums.size(); ++i) {
                res = max(res, f(i, nums, mem));
            }   
            return res + 1;
        }
    

Log in to reply
 

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