LIS general template that can record ALL the LIS [fight.for.dream ]


  • 2
    F

    Update :1234:

    I have implemented the solution that can return all the possible LIS with different position composition as the return result :100:

    
    vector<vector<int>> all_sequenceOfLIS_dp(vector<int>& nums) {
    	vector<vector<int>> result;
    	const int size = nums.size();
    	if (size <= 1)  return vector<vector<int>>{nums};
    	vector<int> dp(size, 1);
    	map<int, vector<int>> prev;
    
    	for (int i = 0; i < size; i++) prev[i] = {};
    	int max_end = 0;
    	int max_len = 1;
    	for (int i = 1; i < size; i++) {
    		for (int j = 0; j < i; j++) {
    			if (nums[j] < nums[i]) {
    				if (dp[j] + 1 > dp[i]) {
    					dp[i] = dp[j] + 1;
    				}
    			}
    		}
    		// add all the possible previous index
    		for (int j = 0; j < i; j++) {
    			if (nums[j] < nums[i]) {
    				if (dp[j] == dp[i] - 1) {
    					prev[i].push_back(j);
    				}
    			}
    		}
    		if (dp[i] > max_len) {
    			max_len = dp[i];
    			max_end = i;
    		}
    	}
    	for (int i = size - 1; i >= 0; i--) {
    		deque<vector<int>> cur_;
    		if (dp[i] == max_len) {	
    			cur_.push_back({i});
    			for (int k = 1; k < max_len; k++) {
    				int cur_size = cur_.size();
    				for (int kk = 0; kk < cur_size; kk++) {
    					vector<int> temp = cur_.front();
    					cur_.pop_front();
    					int endNum = temp.back();
    					for (auto it : prev[endNum]) {
    						temp.push_back(it);
    						cur_.push_back(temp);
    						temp.pop_back();
    					}
    				}
    			}
    			for (auto it : cur_) {
    				result.push_back(it);
    			}
    		}
    	}
    	return result;
    }
    

    Here are the implementation that can return the LIS with the prevIndex array to record the previous smaller index for each node.

        int binary_search(vector<int>& ss, vector<int>& tailIndex, int left, int right, int target) {
            while (right > left) {
            	int mid = left + (right - left) / 2;
            	if (ss[tailIndex[mid]] < target) left = mid + 1;
            	else right = mid;
            }
            return left;
        }
    
    vector<int> sequenceOfLIS(vector<int>& nums) {
    	//tailIndex array : tailIndex[i] record the among all the increasing sequence of length i, the smallest ending element
    	vector<int> tailIndex(nums.size(), 0);
    	//prevIndex array : record the previous smaller number for each inserted number
    	vector<int> prevIndex(nums.size(), 0);
    	vector<int> result;
    	//mark the end of the longest increasing sequence
    	prevIndex[0] = -1;
    	//the nums[0] already processed
    	int len = 1;
    
    	for (int i = 1; i < nums.size(); i++) {
    		//cur number smaller than the start element, replace the start
    		if (nums[i] < nums[tailIndex[0]]) {
    			tailIndex[0] = i;
    		}
    		//cur number bigger than the last element, push it
    		else if (nums[i] > nums[tailIndex[len - 1]]) {
    			prevIndex[i] = tailIndex[len - 1];
    			tailIndex[len++] = i;
    		}
    		//cur number smaller than the last element, find insert position replace it
    		//when the elements at pos is replaced by a smaller element, then the prevIndex[pos] will 
    		else {
    			int pos = binary_search(nums, tailIndex, 0, len - 1, nums[i]);
    			prevIndex[i] = tailIndex[pos - 1];
    			tailIndex[pos] = i;
    		}
    	}
    	//get the longest increasing sequence by the previous index array
    	for (int i = tailIndex[len - 1]; i >= 0; i = prevIndex[i]) {
    		result.push_back(nums[i]);
    	}
    	reverse(result.begin(), result.end());
    	return result;
    }
    
    void solver_test() {
    		int n = 0;
    		cin >> n;
    		vector<int> input(n, 0);
    		for (int i = 0; i < n; i++) cin >> input[i];
    		vector<int> result = sequenceOfLIS(input);
    		for (int i = 0; i < result.size(); i++) cout << result[i] << " ";
    		cout << endl;
    }
    

    For this problem, We do not need to return the sequence but only the length, so we only need the tailIndex array to solve it !

    Here is the implementation with the previsouIndex array parts commented.

        int lengthOfLIS(vector<int>& nums) {
            if (nums.size() <= 1) return nums.size();
            //tailIndex array : tailIndex[i] record the among all the increasing sequence of length i, the smallest ending element
            vector<int> tailIndex(nums.size(), 0);
            //prevIndex array : record the previous smaller number for each inserted number
            //vector<int> prevIndex(nums.size(), 0);
            //vector<int> result;
            //mark the end of the longest increasing sequence
            //prevIndex[0] = -1;
            //the nums[0] already processed
            int len = 1;
            
            for (int i = 1; i < nums.size(); i++) {
            	//cur number smaller than the start element, replace the start
            	if (nums[i] < nums[tailIndex[0]]) {
            		tailIndex[0] = i;
            	}
            	//cur number bigger than the last element, push it
            	else if (nums[i] > nums[tailIndex[len - 1]]) {
            		//prevIndex[i] = tailIndex[len - 1];
            		tailIndex[len++] = i;
            	}
            	//cur number smaller than the last element, find insert position replace it
            	//when the elements at pos is replaced by a smaller element, then the prevIndex[pos] will 
            	else {
            		int pos = binary_search(nums, tailIndex, 0, len - 1, nums[i]);
            		//prevIndex[i] = tailIndex[pos - 1];
            		tailIndex[pos] = i;
            	}
            }
            //get the longest increasing sequence by the previous index array
            //for (int i = tailIndex[len - 1]; i >= 0; i = prevIndex[i]) {
            //	result.push_back(nums[i]);
            //}
            //reverse(result.begin(), result.end());
            //return result;
            return len;
        }
    

  • 0
    F

    We can also use the DP based solution to solve this problem

    
    vector<int> sequenceOfLIS_dp(vector<int>& nums) {
    	const int size = nums.size();
    	if (size <= 1)  return nums;
    	vector<int> dp(size, 1);
    	vector<int> prev(size, -1);
    	vector<int> result;
    	int max_end = 0;
    	int max_len = 1;
    	for (int i = 1; i < size; i++) {
    		for (int j = 0; j < i; j++) {
    			if (nums[j] < nums[i]) {
    				if (dp[j] + 1 > dp[i]) {
    					dp[i] = dp[j] + 1;
    					prev[i] = j;
    				}
    			}
    		}
    		if (dp[i] > max_len) {
    			max_len = dp[i];
    			max_end = i;
    		}
    	}
    	for (int i = max_end; i >= 0; i = prev[i]) {
    		result.push_back(nums[i]);
    	}
    	reverse(result.begin(), result.end());
    	return result;
    }

Log in to reply
 

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