Longest increasing subsequence problem (do you really know it)

Catalog

One . The longest increasing subsequence problem I

Two . The longest increasing subsequence problem II

3、 ... and . The longest increasing subsequence problem III

---

One . The longest increasing subsequence problem I

1. Corresponding Niuke website link

Longest ascending subsequence ( One )_ Niuke Tiba _ Cattle from (nowcoder.com)

2. Title Description ：

 3. Their thinking

1. First of all, we analyze the meaning of the topic ： The longest increasing subsequence is disassembled ： To increase , Or sequence , Not necessarily continuous , Want the longest .

2. We usually think about how to end in a certain position , In this question, we can think like this. We must take i What is the maximum length of the longest increasing subsequence at the end of the position? We do this at each position, so the answer must be in it

Let's say [5,7,1,9,4,6,2,8,3] For example ：

First element 5： The incremental length can only be 1, Next, the second one 7, Than 5 Big , The length is 2

 

The third element 1： There is nothing bigger in front of it , Only for 1 , Fourth element 9, There is 5,7, Therefore, the length is 3 Here you find ,9 Than 7 Big ,7 The length of the forward formation is 2, that 9 You can connect to 7 Behind , Become a new sequence of length plus one .

  I believe Lao tie should understand

4. The corresponding code ：

class Solution {
  public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     *  The length of the longest strictly ascending subsequence of a given array .
     * @param arr int integer vector  Given array 
     * @return int integer 
     */
    int LIS(vector<int>& arr) {
        if (arr.empty())
            return 0;
        // write code here
        int N = arr.size();
        vector<int>dp(N, 1);// The length of the longest increasing subsequence at each position is at least 1 I am myself 
        //dp The meaning of must be in i The maximum length of the longest increasing subsequence at the end of the position 
        int maxLen = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = max(dp[i], dp[j] + 1); // The length of the add 1
                }
            }
            maxLen = max(maxLen, dp[i]);// Update maximum length 
        }
        return maxLen;
    }

};

Two . The longest increasing subsequence problem II

1. Corresponding Niuke website link ：

Longest ascending subsequence ( Two )_ Niuke Tiba _ Cattle from (nowcoder.com)

2. Title Description ：

 3. Their thinking ：

1. Here we introduce end Array ,end[i] The value of is so far, and the length is i+1 The minimum end of

2. Every time I go end Look in the array for greater than or equal arr[i] Leftmost position

 

We see that the same length is 2 The subsequence ,[2,3] Just like [2,5] good . because [2,3] If there is 4 Words , form [2,3,4] Length is 3 了 , however [2,5] Because the conditions are not met , You can't form a team .

When we compose subsequences , Not only should this sequence be as long as possible , And let the rise in the subsequence be as slow as possible ,[2,3] Just like [2,5] Slow rise , In this way, there is a chance to splice longer ascending subsequences . We use an array to save the current longest ascending subsequence , This array is strictly incremented .
Because it is strictly increasing , The last value in the array nums[max] That's the maximum , If you come across another number next time n, It is better than num[max] Even bigger , So obviously , The length of this subsequence is +1, And the array n Add to the end of the array .

[2,3,7,8,11,13,18] It is by far the longest ascending subsequence , Then if you encounter 19, perhaps 101, Because they are all larger than the maximum value in the array 18, So just add it to the end of the array , At the same time, the length of subsequence should be +1.19 and 101 The example of is easy to understand , But if the next number is 6 perhaps 12 Well ？ Because the subsequence should rise as slowly as possible , So let's [2,5,7...] become [2,5,6...] More appropriate , Because the latter rises more slowly . Again , take [...8,11,13,18] become [...8,11,12,18] It also rises more slowly .
That is to say , Known ascending subsequence [i,i_1,i_2,....,i_n], Now we encounter a value in the process of continuing traversal i_k, This value is less than i_n Of , So the length of ascending subsequence remains unchanged . But we need to find a place , take i_k Replace an old value .

Corresponding dynamic diagram ：

4. The corresponding code ：

class Solution {
  public:
    /**
     *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly 
     *
     *  The length of the longest strictly ascending subsequence of the array 
     * @param a int integer vector  Given array 
     * @return int integer 
     */
    int LIS(vector<int>& arr) {
        // write code here
        if (arr.empty()) {
            return 0;
        }
        int N = arr.size();
        vector<int>end(N);
        //end[i] It means that the length so far is i+1 The minimum end of 
        end[0] = arr[0];
        int L = 0;
        int maxLen = 1;
        int right = 0; // Used to control the end Range of array 
        int R = right;
        for (int i = 1; i < N; i++) {
            L = 0;
            R = right;
            while (L <= R) {// Used to find greater than or equal to arr[i] The leftmost position 
                int mid = (L + R) >> 1;
                if (arr[i] > end[mid]) {
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            right = max(right, L); // Update right border 
            maxLen = max(maxLen, L + 1);
            end[L] = arr[i];

        }
        return maxLen;
    }
};

3、 ... and . The longest increasing subsequence problem III

1. Corresponding letecode link ：

Longest ascending subsequence ( 3、 ... and )_ Niuke Tiba _ Cattle from (nowcoder.com)

2. Title Description ：

3. Their thinking

1. This question is only an upgraded version of the previous question. We only need to define a variable record   Just tell me where the end of the longest increasing subsequence is , Then traverse in turn

4. The corresponding code ：

class Solution {
  public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int integer vector the array
     * @return int integer vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        if (arr.empty()) {
            return {};
        }
        int N = arr.size();
        vector<int>dp(N, 1);
        vector<int>end(N);
        int maxLen = 1;
        int maxIndex = 0;
        end[0] = arr[0];
        int right = 0;
        int L = 0;
        int R = right;
        for (int i = 1; i < N; i++) {
            L = 0;
            R = right;
            while (L <= R) {
                int mid = (L + R) >> 1;
                if (arr[i] > end[mid]) {
                    L = mid + 1;
                } else {
                    R = mid - 1;
                }
            }
            right = max(right, L);
            maxLen = max(maxLen, L + 1);
            end[L] = arr[i];
            dp[i] = L + 1;
            if (dp[i] >= maxLen) {// Because it is necessary to minimize the subcriterion 
                maxIndex = i;
                maxLen = dp[i];
            }
        }
        vector<int>ans(maxLen);// Get the longest increasing subsequence 
        for (int i = maxIndex; i >= 0; i--) {
            if (dp[i] == maxLen) {
                ans[--maxLen] = arr[i];
            }
        }
        return ans;
    }
};

Thinking questions ： If you want to get all incremental subsequences ？

#include<iostream>
#include<vector>
using namespace std;
vector<int> process(vector<int>& arr,vector<int>&dp ,int maxLen, int index) {// Get all the longest increasing subsequences 
	vector<int>ans(maxLen);
	for (int i = index; i >= 0; i--) {
		if (dp[i] == maxLen) {
			ans[--maxLen] = arr[i];
		}
	}
	cout << " Come in " << endl;
	return ans;

}
int main() {
	int N;
	cin >> N;
	vector<int>arr(N);
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	vector<int>dp(N, 1);
	vector<int>end(N);
	int maxLen = 1;
	int maxIndex = 0;
	end[0] = arr[0];
	int right = 0;
	int L = 0;
	int R = right;
	for (int i = 1; i < N; i++) {
		L = 0;
		R = right;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (arr[i] > end[mid]) {
				L = mid + 1;
			}
			else {
				R = mid - 1;
			}
		}
		right = max(right, L);
		maxLen = max(maxLen, L + 1);
		end[L] = arr[i];
		dp[i] = L + 1;
		if (dp[i] >= maxLen) {
			maxIndex = i;
			maxLen = dp[i];
		}
	}
	
	vector<vector<int>>ans;
	for (int i = 0; i < N; i++) {
		if (dp[i] == maxLen) {
			ans.push_back(process(arr, dp, maxLen, i));
		}
	}
	for (int i = 0; i < ans.size(); i++) {
		for (int j = 0; j < ans[0].size(); j++) {
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}


	return 0;
}