LIS (longest ascending subsequence) problem that can be understood [easy to understand]

Hello everyone , I meet you again , I'm your friend, Quan Jun .

LIS Introduction to the problem ：

First of all, what is LIS problem ：

There's a long one for n Sequence of numbers a0, a1, ……, a(n-1). Request the length of the longest ascending subsequence in this sequence . Ascending subsequence refers to any i<j All satisfied with ai<aj The subsequence , This problem is called the longest ascending subsequence （LIS,Longest Increasing Subsequence） The famous problem of .

Take a chestnut ： Give you a sequence of （1,5 ,2,6,9,10,3,15）, Then its longest ascending subsequence is ：（1,2,6,9,10,15）

This question uses DP The idea of is easy to solve , Now let's talk about DP（ Dynamic programming ） Thought .

DP brief introduction （ The boss can ignore the content in this title ）

Don't worry for a moment Meeting ！ detailed ！！！ To talk about LIS Problem and its optimization method , For better understanding LIS problem , So let's talk first DP, If you have done some DP You can ignore this introduction DP Explanation , If you are just beginning to contact the suggestion, read it patiently , I believe there will be a great harvest . One 、DP thought ： 1、 Decompose a big problem into subproblems one by one . 2、 If we get the solutions of these subproblems , And then after some treatment , We can get the solution of the original problem . 3、 If these subproblems have the same structure as the original problem , That is, small problems can continue to decompose . 4、 In this way, the big problems are always separated , The scale of the problem is decreasing , Until the subproblem is too small , You'll end up with the youngest problem . 5、 The solution to the minimal problem is obvious , So it recurs back , We can get the solution of the original problem .

Two 、DP The concrete realization of ： 1、 To analyze problems , Get the state transition equation （ Recurrence equation ）. 2、 According to the state transition equation , Start with the atomic problem , Constantly solve upward , Know to get the solution of the original problem . 3、 In the process of constantly solving recursive equations , It's actually a form filling process .

What I just said is hard for me to understand , Too abstract. , For example 2 A chestnut , Let's have a better understanding of DP Thought .

The first chestnut ：//https://vjudge.net/contest/239734#problem/B

Problem description ： Here you are N（N Is odd && 1<=N<=999999） Sequence of Numbers , And guarantee this N One of the numbers M The number of >= （N + 1)/2 , Let you find this number M.

Sample Input: 5 1 3 2 3 3 Sample Output: 3

according to DP Thought , Divide this big problem into several small problems first . So when N by N when , There are at least （N + 1）/ 2 individual M, The other number is left to him ; …… Then when N by 5 It's time , According to the meaning of the title, there must be at least 3 individual M, The other two numbers are left alone ; When N by 3 When , According to the question , There must be two numbers M, The other number is left alone ; First See when N by 1 When , Then this number must be M. So we can delete two different numbers in this sequence （ Delete as long as there are two different numbers ）, The last thing left must be M; Take a chestnut ： intput: 9 3 6 9 3 3 3 8 6 3 loc ： 1 2 3 4 5 6 7 8 9 1、2 Position delete 3、4 Position delete 6、7 Position delete 8、9 Position delete ,, And then there were one 5 Location , that 5 Positional 3 That's what I'm looking for M .

AC Code ：

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
using namespace std;
int arr[1000006];
int dp[1000006];
int main()
{
    int n;
    while(scanf("%d", &n) != EOF){
        memset(arr, 0, sizeof(arr));
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
        int i = 0, j = 1;
        while(j < n){
            if(dp[i] == 1){
                while(dp[i] == 1)
                    i++;
            }
            if(arr[i] != arr[j]){
                i++;
                dp[j++] = 1;
            }
            else if(arr[i] == arr[j]){
                while(arr[i] == arr[j])
                    j++;
            }
        }
        while(dp[i] == 1) i++;
        printf("%d\n", arr[i]);
    }
    return 0;
}

Copy

Another chestnut ：//http://acm.hdu.edu.cn/showproblem.php?pid=2084

This problem is a number tower problem ： There are several towers as shown below , It is required to go from the top to the bottom , If each step can only go to the adjacent node , What is the maximum sum of the number of nodes passing by ？

Input： The input data first includes an integer C, Indicates the number of test instances , The first line of each test instance is an integer N(1 <= N <= 100), Indicates the height of the tower , Next use N A line number means a tower , Among them the first i There's a i It's an integer , And all integers are in intervals [0,99] Inside . Output： For each test case , The maximum sum of possible outputs , The output of each instance takes up one line . Sample Input： 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output： 30

First analyze this topic , Leftmost left / The most right The size of is determined by the upper one , The middle one is decided by the two above . set up i Is the number of layers ,DP thought , Turn a big problem into a sub problem , The big problem is to solve the maximum value of the addition from the top to the bottom , Then the maximum value must be on the last line , Want to find the maximum value of the last line , You have to make sure n – 1 Line inclusion n – 1 Line and its previous maximum , Push it up like this , There is When i == 3 when The third line , In order to ensure as large as possible , Then the middle number has to be chosen , Because the middle can be added to the upper left corner or the upper right corner , Then choose the biggest one and add it to yourself ; When i == 2 when Add the top number to each number in the second line ; When i by 1 When , The biggest thing is himself ,

By analogy , Then the biggest one along the way must be in the last line , Traverse it and get the answer . This tower can be stored in an array , If you expand this array , This question will be more concise ：

（ notes ： The above picture is wrong ,9 Should be changed to 10）

In this way, no matter which row or column , We just need to see which is bigger on the left and right , Just add it to itself , Only in this way can we ensure the journey , When we get to the last line , The last line must have a maximum . From this, we can find the state transition equation （ That is, recursive equation ） dp[ i ][ j ] = max(dp[ i – 1 ][ j ] , dp[ i – 1 ][ j – 1 ]) + arr[ i ][ j ];

AC Code ：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[105][105], arr[105][105], n, c, MAX;
int main()
{
    scanf("%d", &c);
    while(c--){
        MAX = -1;
        memset(dp, 0, sizeof(dp));
        memset(arr, 0, sizeof(arr));
        scanf("%d", &n);
        arr[0][0] = arr[0][1] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                scanf("%d", &arr[i][j]);
                arr[i][0] = 0;
                arr[i][i + 1] = 0;
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i][j] = arr[i][j];
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j];
            }
        }
        for(int i = 1; i <= n; i++)
            MAX = max(MAX, dp[n][i]);
        printf("%d\n", MAX);
    }
}

Copy

After you understand this problem, you can try to rely on yourself AC A question , This topic is basically the same as this type , It's just a little bit harder than this , But it can deepen understanding . Address ：https://vjudge.net/contest/239734#problem/G

LIS Detailed explanation ：

First, let's explain his recursive relation ： Definition dp[ i ] by ： With ai Is the length of the longest ascending subsequence at the end . that dp[ i ] What does it contain ？

situation 1`: Only include itself , That is to say, all the elements in front of it are bigger than him ; Take a chestnut ： A sequence （7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7） that dp[ 6 ] == 1;

situation 2`： In order to ensure that the ascending subsequence is as long as possible , Then there is dp[ i ] As big as possible , But promise again dp[ i ] On the largest possible basis , It must also meet the rise of the sequence ; So dp[ i ] = max ( 1 , dp[ j ] + 1 ) { j < i && aj < ai } . there 1 Is that when ai When the previous numbers are bigger than him , He himself is a subsequence ;dp[ j ] + 1 refer to ： When the first i There is one in front of the number The first j The number satisfies aj < ai also j < i At this time, it means ai Elements can be inherited in aj After the element, increase the length of the subsequence as much as possible .

take j from 1 Traversing i – 1 , In between , Find the largest possible dp[ i ] That is, the length of the longest ascending subsequence ( At the prompt dp[n] Not necessarily the longest subsequence ,n Is the number of numbers in the sequence , For example, the sequence [ 2, 3, 4, 5, 1 ],dp[5] = 1( By subsequence [1] constitute ), However dp[4] = 4( By subsequence [2,3,4,5] constitute ) )

The above is still a little general , Then take another chestnut ： Still use the sequence just now ：（7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7）

In the beginning a1 = 7, Make dp[ 1 ] = 1; Then look at the next element a2 = 9, Make dp[ 2 ] = 1, Then it needs to be checked i Whether there is one smaller than him in front because a1 < a2 and dp[ 1 ] + 1 > dp[ 2 ], therefore dp[ 2 ] = dp[ 1 ] + 1 == 2; Then look at the next element a3 = 6, Make dp[ 3 ] = 1, Then you need to check the previous elements a1 And a2 Is there anyone smaller than him , There is no such thing as , Spicy? up to now , The subsequence is himself . Then look at the next element a4 = 10; Make dp[ 4 ] = 1; Then you need to check the previous elements in turn a1 And a2 And a3 Is there anyone smaller than him , Take a look a1 Smaller than it , And ,dp[ 1 ] + 1 > dp[ 4 ] So dp[ 4 ] = dp[ 1 ] + 1 == 2, That at this time a1 And a4 Can form a length of 2 The ascending subsequence of , Let's see if we can form longer subsequences , So let's take a look again a2 , a2 < a4 And dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 So dp[ 4 ] = dp[ 2 ] + 1 == 3, the a4 Undertake in a2 Later than in a1 Better after , Undertake in a2 The following sequence is ：a1 a2 a4 , Form a length of 3 The ascending subsequence of ; Then I'll see a3 , a3 < a4 But it's a pity d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , So you can't put a4 Add to a3 Behind . Then repeat the above process , Find the biggest dp [ i ] Then this number is the longest ascending subsequence . The code implementation is as follows ：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int arr[500], n, dp[500], ans = -1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i]); // Not recommended for use cin cout  When they execute, they have to analyze the data type first , Time ratio  scanf printf   Much more , Many questions are overtime because of this place , Lead to a penalty when the game 
    /*  The core code for solving the number of the longest subsequence  */
    /* ********************************************** */
    for(int i = 1; i <= n; i++){
        dp[i] = 1; // initialization 
        for(int j = 1; j < i; j++){
            if(arr[j] < arr[i]) //  If the maximum descent subsequence is found, the opposite is true 
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(dp[i], ans);
    }
    /* ********************************************** */

    printf(" The number of longest subsequences is ： %d", ans);
    return 0;
}
/*
 Examples ：
7
7 9 6 10 7 1 3
 The number of longest subsequences is ： 3
*/

Copy

Is that over ？ If this is the end, it is not called detailed explanation ~ I'll talk slowly later , Its optimization and its method of marking paths .

Take a break , Now that you've learned, let's practice with a few templates ！（ There will be problem solving , Try it yourself first ！） https://vjudge.net/contest/218661#problem/A

Change the title to a template Title , Directly solve the longest ascending subsequence AC Code ：

//https://vjudge.net/contest/218661#problem/A
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int n, arr[1005], ans = -1, dp[1005];
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    for(int i = 1; i <=n; i++){
        dp[i] = 1;
        for(int j = 1; j < i; j++){
            if(arr[j] < arr[i])
                dp[i] = max(dp[i], dp[j] + 1);
        }
        ans = max(dp[i], ans);
    }
    printf("%d", ans);
    return 0;
}

Copy

https://vjudge.net/contest/239734#problem/E

This question is also a template question , Go straight to the code ：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1005], n, MAX;
int arr[1005];
int main()
{
    while(scanf("%d", &n) != EOF){
        if(n == 0) break;
        MAX = -1;
        for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
        for(int i = 0; i < n; i++){
            dp[i] = arr[i];
            for(int j = 0 ; j < i; j++){
                if(dp[i] < dp[j] + arr[i] && arr[i] > arr[j]){
                    dp[i] = dp[j] + arr[i];
                }
                MAX = max(dp[i], MAX);
            }
        }
        printf("%d\n", MAX);
    }
    return 0;
}

Copy

It's about finding out Vjudge Jumping again ... Another topic from Luogu , A few more may be added later Vjudge The subject of https://www.luogu.org/problemnew/show/P1091

Title Description

NNN Three students stand in a row , The music teacher is going to invite one of them ( N−KN-KN−K ) Three students came out , Make the rest KKK Three students form a chorus .

Chorus formation refers to such a formation ： set up K The students are numbered from left to right 1,2,…,K1,2,…,K1,2,…,K , Their heights are T1,T2,…,TKT_1,T_2,…,T_KT1​,T2​,…,TK​ , Then their height is satisfied T1<…<Ti>Ti+1>…>TK(1≤i≤K)T_1<…<T_i>T_{i+1}>…>T_K(1 \le i \le K)T1​<…<Ti​>Ti+1​>…>TK​(1≤i≤K) .

Your task is , All known N The height of a classmate , At least a few students are required for calculation , It can make the rest of the students form a chorus .

I / O format

Input format ：

Two lines in total .

The first line is an integer N(2≤N≤100)N(2 \le N \le 100)N(2≤N≤100) , Represents the total number of students .

The second line has nnn It's an integer , Separate... With spaces , The first iii It's an integer Ti(130≤Ti≤230)T_i(130 \le T_i \le 230)Ti​(130≤Ti​≤230) It's No iii The height of a classmate ( centimeter ).

Output format ：

An integer , At least a few students are required to stand out .

Sample input ： 8 186 186 150 200 160 130 197 220

Sample output ： 4

Answer key ： What he means is that he wants to keep students as much as possible . And the height is high in the middle and low on both sides , So if the tallest one is on the far left , Then it is enough to directly find the longest ascending sequence , If it's on the left , Then it is enough to find the longest ascending sequence directly from the right , But I'm not sure where the highest one is most suitable . Now the key As long as the highest one is determined , Find his longest ascending subsequence from the leftmost and his longest ascending and descending subsequence from the rightmost , This will ensure that the largest number of people remain , In other words, the number of people eliminated is the least . set up dp_1[ i ] To rise from the left i The highest rising number of students , dp_2[ n – i ] For descending from the right i The highest rising number of students , Sum up dp_3[ i ] = dp_1[ i ] + dp_2[ i ] So the biggest dp_3[ i ] , Take this as the end point, and the left side is lower , The right side is also lower , Then the maximum number of people left is dp_3[ i ] – 1 Subtract what he repeated twice chestnuts ：

Serial number i ： 1 2 3 4 5 6 7 8 height 186 186 150 200 160 130 197 220 Rise from the left dp_1[ i ] = 1 1 1 2 2 1 3 3 Go up and down from the right dp_2[ i ] = 4 4 2 3 2 1 1 1 The sum of the dp_3[ i ] = 5 5 3 5 4 2 4 4

In order to ensure as many as possible on the left in the middle , As many as possible on the right , So choose The sum of the dp_3[ i ] maximal Here is the When i == 1 || i == 2 || i == 4 When dp_3[ i ] – 1 == 4 （ Subtract what he repeated himself ）, So the answer is 8 – 4 == 4 , Because subtracting the most left , That's the answer ~ AC Code ：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int N, arr[105], dp[105] = {0}, dp2[105] = {0}, dp_all[105] = {0};
    scanf("%d", &N);
    for(int i = 0; i < N; i++) scanf("%d", &arr[i]);
    for(int i = 0; i < N; i++){  // Find the longest ascending subsequence 
        dp[i] = 1;
        for(int j = 0; j < i; j++){
            if(arr[j] < arr[i] && dp[i] < dp[j] + 1)
                dp[i] = dp[j] + 1;
        }
    }
    for(int i = N - 1; i >= 0; i--){  // Find the longest ascending subsequence from back to front 
        dp2[i] = 1;
        for(int j = N - 1; j > i; j--){
            if(arr[j] < arr[i] && dp2[i] < dp2[j] + 1)
                dp2[i] = dp2[j] + 1;
        }
    }
    int MAX = -1;
    for(int i = 0; i < N; i++){
        dp_all[i] = dp[i] + dp2[i];
        MAX = max(MAX, dp_all[i]);
    }
    printf("%d", N - MAX + 1);
    return 0;
}

Copy

LIS Of nlogn The optimization of the ： LIS To put it bluntly, it is actually a greedy algorithm , For example, let's ask you to find a longest ascending subsequence to put , Let's walk together .

for instance （4, 2, 3, 1, 2,3,5） This sequence , Find his longest ascending subsequence , So look at , If the longest ascending sequence is found , Then according to greed , It should be most possible to make the elements of the sequence smaller as a whole , So that more elements can be added . Now open up a new array ,arr[ 10 ], { …….} –> This is his space , Now start to simulate the greedy algorithm to solve the longest ascending subsequence , The first number is 4, Add it first , So for { 4 } Let's look at the next number 2, It is better than 4 Small , So if he and 4 Whether replacement can make the current subsequence （ He is a subsequence of this element ） To become smaller , It's more convenient to add elements in the future ？ Yes . At the same time, it also ensures that the length of the sequence remains unchanged , Therefore, replacing a large number with a small one can make the whole sequence smaller on the premise that the sequence length remains unchanged , Easier to add elements . So now for { 2 } Let's look at his next element 3, He is better than 2 Big , So, add it behind him ,{ 2, 3} The next element is 1, It is better than 3 smaller , So, in order to ensure that the whole subsequence is as small as possible （ So that more elements can be added ）, Find the first number larger than him from the current sequence and replace it , Then it becomes { 1, 3}, continue .. The next number is 2, Then the sequence becomes { 1,2}, The next number is 3, Then the sequence is {1,2,3}, The next number is 5, Then the sequence is {1,2,3,5}, End . Now in the sequence 4 Elements , So the number of his longest subsequence is 4, But this sequence is a pseudo sequence , The elements inside , Not really the longest ascending subsequence , It is only the same as the number of the longest ascending subsequence . Because the binary search is used when searching , So the time complexity is o（nlogn）.

Implementation code ：

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{
    int arr[500], n, dp[500], ans = -1;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    /*  The core code for solving the number of the longest subsequence  */
    /* ********************************************** */
    int k = 1;
    dp[k] = arr[1];
    for(int i = 2; i <= n; i++){
        if(dp[k] < arr[i]) dp[++k] = arr[i]; // If it's bigger than the last element , Then add at the end 
        else *(lower_bound(dp + 1, dp + 1 + k, arr[i])) = arr[i]; // If it is smaller than the last element , Then replace the first larger number in the sequence ;
    }
    /* ********************************************** */

    printf(" The number of longest subsequences is ： %d", k);
    return 0;
}

Copy

Tag path ：

O( ) Algorithm marking path , Just use an array of record precursors pre that will do .

Still use the sequence just now ：（7, 9, 6, 10, 7, 1, 3） Respectively （a1, a2, a3, a4, a5, a6, a7）

In the beginning a1 = 7, Make dp[ 1 ] = 1, pre[1] = 1; Then look at the next element a2 = 9, Make dp[ 2 ] = 1, pre[2] = 2, Then it needs to be checked i Whether there is one smaller than him in front because a1 < a2 and dp[ 1 ] + 1 > dp[ 2 ], therefore dp[ 2 ] = dp[ 1 ] + 1 == 2, Also update the tag pre[2] = 1; Then look at the next element a3 = 6, Make dp[ 3 ] = 1, pre[3] = 3, Then you need to check the previous elements a1 And a2 Is there anyone smaller than him , There is no such thing as , Spicy? up to now , The subsequence is himself . Then look at the next element a4 = 10; Make dp[ 4 ] = 1, pre[4] = 4; Then you need to check the previous elements in turn a1 And a2 And a3 Is there anyone smaller than him , Take a look a1 Smaller than it , And ,dp[ 1 ] + 1 > dp[ 4 ] So dp[ 4 ] = dp[ 1 ] + 1 == 2, pre[4] = 1, That at this time a1 And a4 Can form a length of 2 The ascending subsequence of , Let's see if we can form longer subsequences , So let's take a look again a2 , a2 < a4 And dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 So dp[ 4 ] = dp[ 2 ] + 1 == 3, pre[4] = 2, the a4 Undertake in a2 Later than in a1 Better after , Undertake in a2 The following sequence is ：a1 a2 a4 , Form a length of 3 The ascending subsequence of ; Then I'll see a3 , a3 < a4 But it's a pity d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , So you can't put a4 Add to a3 Behind . Then repeat the above process , Update all pre.

dp 1 2 1 3 2 1 2 pre 1 1 3 2 3 6 6

maximal dp The value is 3, So the longest subsequence length is 3, The last element is 4 Location . The trace path is ：4 -> pre[4] == 2 -> pre[2] == 1 -> pre[1] == 1( stop it ) Path is 4,2,1, This is flashback , Because I looked for it from the back .

Topic linking ：http://acm.hdu.edu.cn/showproblem.php?pid=1160 A classic LIS The topic of path marking .

The question ： give n A mouse . Each mouse has a corresponding weight and speed. Now it needs to come from here n In the sequence of mice , Find the longest sequence , Satisfy the mouse weight Strictly increasing ,speed Strictly decreasing , There may be weight and speed All the same mice .

Answer key ： Let's follow speed Descending sort , The rest just need to find weight Strictly increasing subsequences of , So it turns to the problem of finding the longest ascending subsequence .

#include<bits/stdc++.h>
#define up(i, x, y) for(ll i = x; i <= y; i++)
#define down(i, x, y) for(ll i = x; i >= y; i--)
#define bug printf("***************************\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lk k<<1
#define rk k<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;
const double pi = acos(-1);
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;

int cnt, ans, loc, x, y;
int dp[maxn], pre[maxn], path[maxn];

struct node
{
	int w, v, id;
}a[maxn];

bool cmp(node a, node b)
{
	if(a.v != b.v)
		return a.v > b.v;
	return a.w < b.w;
}

int main(int argc, char const *argv[])
{
	while(cin >> x >> y)
	{
		a[++cnt].w = x;
		a[cnt].v = y;
		a[cnt].id = cnt;
	}

	sort(a + 1, a + 1 + cnt, cmp);

	for(int i = 1; i <= cnt; ++i)
	{
		dp[i] = 1;
		pre[i] = i; //  initialization , Take one element as a subsequence , Then your precursor node is yourself  
		for(int j = 1; j < i; ++j)
		{
			if(a[j].w < a[i].w && dp[i] < dp[j] + 1 && a[j].v != a[i].v) 
			//1.  Satisfy w Monotonic strictly increasing  2.  Can be updated  3. Because the speed is strictly monotonically decreasing , So add  dp[j].v != d[i].v  This condition 
			{
				dp[i] = dp[j] + 1; //  The current sequence is  ai  Undertake in  aj  after , therefore  ai  The precursor node of is  j  node 
				pre[i] = j; //  Change the precursor node 
			}

			if(ans < dp[i]) //  Update the length of the longest subsequence of the record , And the position of the element at the end of the longest subsequence 
			{
				ans = dp[i]; //  Update the length of the longest subsequence of the record 
				loc = i;   	 //  Update the position of the element at the end of the longest subsequence , To facilitate the output path 
			}
		}
	}

	for(int i = 1; i <= ans; i++)
	{
		path[i] = a[loc].id; //  Need to record the original real location , So here it is path Fu is  id,  No loc
		loc = pre[loc]; //  Search according to the precursor array of records 
	}//  The path here is from back to front , Pay attention to the reverse when outputting 

	printf("%d\n", ans);
	for(int i = ans; i >= 1; i--)
	{
		printf("%d\n", path[i]);
	}
	return 0;
}

Copy

nlogn Path marking of Algorithm ： The first thing to be clear is through nlogn The final sequence obtained by the algorithm is chaotic , Only the length of the sequence is valuable , So the last sequence is not a path . However, we can mark the actual position in the update process , Finally get the desired path . Just give an example . use mp The position of the array record in the sequence .

for instance （4, 2, 3, 1, 2,3,5） This sequence , Find his longest ascending subsequence , So look at , If the longest ascending sequence is found , Then according to greed , It should be most possible to make the elements of the sequence smaller as a whole , So that more elements can be added . Now open up a new array ,arr[ 10 ], { …….} –> This is his space , Now start to simulate the greedy algorithm to solve the longest ascending subsequence , The first number is 4, Add it first , So for { 4 }, And then mp[1] = 1, because a1 In the sequence is in the first position , therefore mp[1] = 1. Let's look at the next number 2, It is better than 4 Small , So if he and 4 Whether replacement can make the current subsequence （ He is a subsequence of this element ） To become smaller , It's more convenient to add elements in the future ？ Yes . So now for { 2 } And then mp[2] = 1, because a2 It is still in the first position in the sequence , therefore mp[2] = 1. Let's look at his next element 3, He is better than 2 Big , So, add it behind him ,{ 2, 3} And then mp[3] = 2, because a2 In the sequence, it is in the 2 A place , therefore mp[3] = 2. The next element is 1, It is better than 3 smaller , So, in order to ensure that the whole subsequence is as small as possible （ So that more elements can be added ）, Find the first number larger than him from the current sequence and replace it , Then it becomes { 1, 3} And then mp[4] = 1, because a4 In the sequence is in the first position , therefore mp[4] = 1, continue . The next number is 2, Then the sequence becomes { 1,2} And then mp[5] = 2, because a5 In the sequence, it is in the 2 A place , therefore mp[5] = 2, The next number is 3, Then the sequence is {1,2,3} And then mp[6] = 3, because a6 In the sequence, it is in the 3 A place , therefore mp[6] = 3, The next number is 5, Then the sequence is {1,2,3,5} And then mp[7] = 4, because a7 In the sequence, it is in the 4 A place , therefore mp[7] = 4, End . Now in the sequence 4 Elements , So the number of his longest subsequence is 4, But this sequence is a pseudo sequence , The elements inside , Not really the longest ascending subsequence , It is only the same as the number of the longest ascending subsequence . Because the binary search is used when searching , So the time complexity is o（nlogn）.

Sequence ： 4, 2, 3, 1, 2, 3, 5 mp: 1 1 2 1 2 3 4

//  So look from the far right to the left ：
for(int i = n; i >= 1; i--)
{
    if(mp[i] == top) // top  Is the length of the longest subsequence 
        path[top--] = i;  // path  The path of the record 
}

//  Here the path is ： 4 5 6 7

Copy

Topic linking ：http://acm.hdu.edu.cn/showproblem.php?pid=1160 Like the example above, it is just for practice nlogn The algorithm of .

#include<bits/stdc++.h>
#define up(i, x, y) for(ll i = x; i <= y; i++)
#define down(i, x, y) for(ll i = x; i >= y; i--)
#define bug printf("***************************\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define lk k<<1
#define rk k<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double eps = 1e-8;
const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;
const double pi = acos(-1);
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
using namespace std;

int top, ans, len, x, y;
int st[maxn], mp[maxn], path[maxn];

struct node
{
	int w, v, id;
}a[maxn];

bool cmp(node a, node b)
{
	if(a.v != b.v)
		return a.v > b.v;
	return a.w < b.w;
}

int main(int argc, char const *argv[])
{
	while(cin >> x >> y)
	{
		a[++len].w = x;
		a[len].v = y;
		a[len].id = len;
	}

	sort(a + 1, a + 1 + len, cmp);

	top = 0;
	st[++top] = a[1].w; //  Push the first element onto the stack 
	mp[a[1].id] = 1;    //  Determine the position of the first element 
	for(int i = 2; i <= len; ++i)
	{
		if(a[i].w > st[top]) //  If the current value is greater than the element at the top of the stack 
		{
			st[++top] = a[i].w; //  Join the stack 
			mp[a[i].id] = top;  //  Mark the actual position in the stack , It is convenient to find the path later 
		}
		else
		{
			int l = 1, r = top;  //  Binary search for the first ratio  a[i].w  Big elements , To replace 
			while(l <= r)
			{
				int mid = (l + r) >> 1;
				if(st[mid] < a[i].w)
				{
					l = mid + 1;
				}
				else
				{
					r = mid - 1;
				}
			}
			st[l] = a[i].w; //  Replace 
			mp[a[i].id] = l;  //  Record the actual position in the stack 
		}
	}

	ans = top;
	for(int i = len; i >= 1; i--)
	{
		if(mp[a[i].id] == top)      // Find the path according to the location 
			path[top--] = a[i].id; 
	}

	printf("%d\n", ans);
	for(int i = 1; i <= ans; i++)
	{
		printf("%d\n", path[i]);
	}

	return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/130480.html Link to the original text ：https://javaforall.cn