How can I count the number of longest increasing LIS by evolving my recursive solution for example [1,3,5,4,7] returns 2 where the LIS is 1,3,5,7 and 1,3,4,7similarly for [3,3,3,3] it will be 4 where LIS is 3 and there are 4 of them
I compute LIS recursively as follows: (I can optimize this using memoisation and go further to DP and then to a segmented tree as per various solutions but I would like to intuitively lead myself to them)
int numberOfLis(vector<int>& nums) { //Set the size of count to the size of num, since there cannot be an LIS greater than the size of nums vector<int> count(nums.size(), 0); //Get the size of the maximum LIS and update the frequency of how many similar sizes have been encountered in the count array int maxcount = LIS(nums, INT32_MIN, 0, count); //Return the number of occurances by looking it up in our count. return count[maxcount]; } int LIS(vector<int>& nums, int prev, int index, vector<int>& count) { if (index == nums.size()) return 0; int with = 0; //Increasing sequence, lets select it. if (nums[index] > prev) with = 1 + helper(nums, nums[index], index + 1, count); //See if we can do better without the current number int without = helper(nums, prev, index + 1, count); //Get the maximum seen so far and update the frequency in count array int maxcount = max(with, without); ++count[maxcount]; return maxcount; } I used a count array vector<int>(nums.size(), 0) to increment the max value as I encounter it as ++count[max(with,without)] where the count of the returned max value would be the answer. This lead the count array to have 4 a count of 1 not 2 which is wrong. I am looking for a way to move forward from here.
Updated: Added code for the count array and added comments
2 Answers
Answers 1
The count for a subsequence is more than an increment, as there can be multiple subsequences that end up with the same length.
Working with your example data, when index is 1, both with and without are 3. count[3] is only incremented once, though, even though there are two subsequences with this length, and 3 is returned as the maximum length. When this is used by the previous call (when index is 0), with will be 4 and without 3. count[4] is only increased by 1, even though there are two subsequences of length 4.
You need to change helper to return not just the length of the longest subsequence, but the number of subsequences that have that length.
Answers 2
First, calculate the longest increasing subsequence length starting at kth element of the array.
Then, using this data use something like:
int numberoflis(int k){ if(LIS(k)==1) return 1; int ret = 0; for(int i=k+1; i<N; ++i){ if(A[i] > A[k] && LIS(i) == LIS(k)-1){ ret += numberoflis(i); } } return ret; } Now you have number of longest increasing subsequences starting at point k. Use a simple loop to figure out the total number of LISs. Also, you should memoize this - but it is easy.
0 comments:
Post a Comment