都能看懂的LIS（最长上升子序列）问题[通俗易懂]
都能看懂的LIS（最长上升子序列）问题[通俗易懂]
大家好，又见面了，我是你们的朋友全栈君。
LIS问题介绍：
首先来说一下什么是LIS问题：
有一个长为n的数列a0, a1, ……, a(n-1)。请求出这个序列中最长的上升子序列的长度。上升子序列指的是对于任意的i<j都满足ai<aj的子序列，该问题被称为最长上升子序列（LIS，Longest Increasing Subsequence）的著名问题。
举个栗子：给你一个序列为（1，5 ，2，6，9，10，3，15），那么它的最长上升子序列为：（1，2，6，9，10，15）
这个问题用DP的思想很容易解决，那么现在再来说一下DP（动态规划）的思想。
DP简介（大佬可以忽略此标题里的内容）
别急一会 会！详！！！谈LIS问题以及它的优化方法，为了更好的理解LIS问题，所以先来谈一下DP，如果做过一些DP的题的可以忽略这段入门DP的讲解，如果刚开始接触建议耐心读完，相信会有很大收获。 一、DP思想： 1、把一个大的问题分解成一个一个的子问题。 2、如果得到了这些子问题的解，然后经过一定的处理，就可以得到原问题的解。 3、如果这些子问题与原问题有着结构相同，即小问题还可以继续的分解。 4、这样一直把大的问题一直分下去，问题的规模不断地减小，直到子问题小到不能再小，最终会得到最小子问题。 5、最小子问题的解显而易见，这样递推回去，就可以得到原问题的解。
二、DP的具体实现： 1、分析问题，得到状态转换方程（递推方程）。 2、根据状态转换方程，从原子问题开始，不断的向上求解，知道得到原问题的解。 3、在通过递推方程不断求解的过程，实际上是一个填表的过程。
刚才说的我自己都觉得不好理解，太抽象了，为此举个2个栗子，让大家更好的理解DP的思想。
第一个栗子：//https://vjudge.net/contest/239734#problem/B
问题描述：给你一个有N（N是奇数 && 1<=N<=999999）个数的序列，而且保证这N个数中有一个数M的数量 >= （N + 1)/2 ，让你找出这个数M。
Sample Input: 5 1 3 2 3 3 Sample Output: 3
按照DP的思想，把这个大问题先分解成若干个小问题。所以呢当N为N时，至少有（N + 1）/ 2个M，另外的数就先不管他； ……然后当N为5得时候，依据题意那么一定至少有3个M，另外两个数就先不管他；当N为3的时候，根据题意得，一定有两个数为M，另外一个数就先不管他；先 来看当N为1的时候，那么这个数一定是M。所以就可以把这个序列中得两个不同的数删去（只要有两个数不同就删去），最后剩下的一定是M； 举个栗子： intput: 9 3 6 9 3 3 3 8 6 3 loc ： 1 2 3 4 5 6 7 8 9 1、2位置删去 3、4位置删去 6、7位置删去 8、9位置删去，，还剩一个5位置，那么5位置的 3 就是要找的M .
AC代码：
#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;
}再来个栗子：//http://acm.hdu.edu.cn/showproblem.php?pid=2084
该问题是一个数塔问题： 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
Input：输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1 <= N <= 100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。 Output：对于每个测试实例，输出可能得到的最大和，每个实例的输出占一行。 Sample Input： 1 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Sample Output： 30
先分析一下这个题目，最左/最右 的大小是由其上面一个决定，中间的是由其上面的两个决定。 设i为层数，DP思想，把大问题化成子问题，大问题是求解从上面到最底下这一路的加和的最大值，那么最大值一定在最后一行，想找到最后一行的最大值，就得保证 n – 1 行包含 n – 1 行及其之前的最大值，这样递推上去，就有 当i == 3时 第三行，为了保证尽可能大，那么这时候中间的一个数就得选择了，因为中间的既可以加左上角的也可以加右上角的，那么就选一个最大的加在自己的身上；当i == 2时 第二行的每个数都加上最上面的数；当i为1的时候，最大就是他自己，
依次类推，那么这一路走来最大的一定在最后一行，遍历一下就得出答案了。 这个塔可以用数组存起来，如果把这个数组扩展一下，这个问题将更加简洁：
（注：上图的写错了，9应该改为10）
这样一来不管第几行第几列，都只需要看它的左上和正上哪一个大，就加到本身，这样才能保证一路走来，走到最后一行的时候，最后一行一定存在最大值。 由此可以找出状态转移方程（也就是递推方程） dp[ i ][ j ] = max(dp[ i – 1 ][ j ] , dp[ i – 1 ][ j – 1 ]) + arr[ i ][ j ];
AC代码：
#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);
}
}大家明白了这道题后可以自己尝试依靠自己AC一道题目，该题目和这个类型基本一样，就是比这个略微难一点点，但是可以加深理解。 地址：https://vjudge.net/contest/239734#problem/G
LIS详解：
首先我们来讲解一下他的递推关系式： 定义dp[ i ] 为：以 ai 为末尾的最长上升子序列的长度。 那么dp[ i ] 包含什么呢？
情况1`: 只包含它自己，也就是说它前面的元素全部都比他大；举个栗子：一个序列（7， 9， 6， 10， 7， 1， 3）分别为 （a1, a2, a3, a4, a5, a6, a7）那么dp[ 6 ] == 1;
情况2`：为了保证上升子序列尽可能的长，那么就有 dp[ i ] 尽可能的大， 但是再保证 dp[ i ] 尽可能大的基础上，还必须满足序列的上升； 所以呢 dp[ i ] = max ( 1 , dp[ j ] + 1 ) { j < i && aj < ai } 。这里的1就是当 ai 前面的数都比他大的时候，他自己为一个子序列；dp[ j ] + 1 指的是： 当第 i 个数前面有一个 第 j 个数满足 aj < ai 并且 j < i 这时候就说明 ai 元素可以承接在 aj 元素后面来尽可能的增加子序列的长度。
将 j 从 1 遍历到 i – 1 ，在这之间，找出尽可能大的dp[ i ]即为最长上升子序列的长度(提示下 dp[n] 不一定是最长的子序列，n为数列中数的个数，例如序列 [ 2, 3, 4, 5, 1 ]，dp[5] = 1(由子序列[1]构成)，然而 dp[4] = 4(由子序列 [2,3,4,5] 构成) )
上面说的还是有点笼统， 那么再举个栗子吧： 还是用刚才的序列：（7， 9， 6， 10， 7， 1， 3）分别为 （a1, a2, a3, a4, a5, a6, a7）
最开始a1 = 7, 令dp[ 1 ] = 1； 然后看下一个元素 a2 = 9, 令dp[ 2 ] = 1, 那么需要检查 i 前面是否有比他小的 因为 a1 < a2 而且 dp[ 1 ] + 1 > dp[ 2 ], 所以dp[ 2 ] = dp[ 1 ] + 1 == 2; 然后再看下一个元素 a3 = 6, 令 dp[ 3 ] = 1, 那么需要检查前面的元素 a1 与 a2 是否有比他小的， 一看没有，辣么 到目前为止，子序列就是他自己。 然后再看一下下一个元素 a4 = 10; 令 dp[ 4 ] = 1; 那么需要依次检查前面的元素 a1 与 a2 与 a3 是否有比他小的 , 一看a1比它小，而且呢，dp[ 1 ] + 1 > dp[ 4 ] 所以呢 dp[ 4 ] = dp[ 1 ] + 1 == 2, 说明此时 a1 与 a4 可以构成一个长度为 2 的上升子序列，再来看看还可不可以构成更长的子序列呢，所以咱们再来看看 a2 , a2 < a4 而且呢 dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 所以呢dp[ 4 ] = dp[ 2 ] + 1 == 3, 即将a4承接在a2后面比承接在a1后更好，承接在a2后面的序列为：a1 a2 a4 ，构成一个长度为 3 的上升子序列; 然后再来看 a3 , a3 < a4 但是可惜的是 d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , 所以呢就不能把a4加在a3的后面 。 然后就是重复上述过程，找到最大的dp [ i ] 那么这个数就是最长上升子序列。 代码实现如下：
#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]); //不建议用cin cout 他们执行的时候还得先分析数据类型，耗时比 scanf printf 多好多，很多题目就因为这个地方而超时，导致比赛的时候罚时
/* 求解最长子序列的个数的核心代码 */
/* ********************************************** */
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;
}
/*
样例：
7
7 9 6 10 7 1 3
最长子序列的个数为： 3
*/这样就完了吗？如果这样就完了就不叫详解啦~ 一会会慢慢讲，它的优化还有他的标记路径的方法。
先歇会，既然学了就来几道模板提练练手把！（都会有题解哒，先自己来一边试试！） https://vjudge.net/contest/218661#problem/A
改题目为一个模板题，直接求解最长上升子序列即可 AC代码：
//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;
}https://vjudge.net/contest/239734#problem/E
该题也是模板题，直接上代码：
#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;
}写着写着突然发现Vjudge又蹦了。。。 又从洛谷上找的题目，后续可能会再加上几个Vjudge的题目 https://www.luogu.org/problemnew/show/P1091
题目描述
NNN 位同学站成一排，音乐老师要请其中的( N−KN-KN−K )位同学出列，使得剩下的 KKK 位同学排成合唱队形。
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为 1,2,…,K1,2,…,K1,2,…,K ，他们的身高分别为 T1,T2,…,TKT_1,T_2,…,T_KT1,T2,…,TK ， 则他们的身高满足 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) 。
你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。
输入输出格式
输入格式：
共二行。
第一行是一个整数 N(2≤N≤100)N(2 \le N \le 100)N(2≤N≤100) ，表示同学的总数。
第二行有 nnn 个整数，用空格分隔，第 iii 个整数 Ti(130≤Ti≤230)T_i(130 \le T_i \le 230)Ti(130≤Ti≤230) 是第 iii 位同学的身高(厘米)。
输出格式：
一个整数，最少需要几位同学出列。
Sample input ： 8 186 186 150 200 160 130 197 220
Sample output ： 4
题解：他的意思就是说想尽可能的留下学生。而且身高是中间高两边低的，那么如果说最高的要是在最左边，那么直接求他的最长上升子序列就够了，如果说在左边，那么直接从右边求他的最长上升子序列就够了，但是呢不确定最高的在哪里最合适。 现在关键 只要确定了最高的那个，求他的从最左边的最长上升子序列和他从最右边的最长升降子序列，这样就可以保证留下的人数最多，换句话地说就是剔除的人数最少。设dp_1[ i ] 为从左边上升第 i 个学生的最高上升的个数， dp_2[ n – i ] 为从右边上降第 i 个学生的最高上升的个数，求和 dp_3[ i ] = dp_1[ i ] + dp_2[ i ] 那么最大的 dp_3[ i ] ，以这个为终点左边依次低，右边也依次低， 那么最多留下人数就是 dp_3[ i ] – 1 减去他自己重复了两遍的 栗子：
序号 i ： 1 2 3 4 5 6 7 8 身高 186 186 150 200 160 130 197 220 从左边上升dp_1[ i ] = 1 1 1 2 2 1 3 3 从右边上降dp_2[ i ] = 4 4 2 3 2 1 1 1 总和dp_3[ i ] = 5 5 3 5 4 2 4 4
为了保证中间的左边的尽可能多，右边的也尽可能多，所以选择 总和 dp_3[ i ] 最大的 这里就是 当i == 1 || i == 2 || i == 4的时候 dp_3[ i ] – 1 == 4 （减去他自己重复的一遍）, 所以答案是 8 – 4 == 4 , 因为减去留下的最多的，就是答案咯~ AC代码：
#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++){ //求最长上升子序列
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--){ //从后往前求最长上升子序列
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;
}LIS的nlogn的优化： LIS的优化说白了其实是贪心算法，比如说让你求一个最长上升子序列把，一起走一遍。
比如说（4, 2, 3, 1, 2，3，5）这个序列，求他的最长上升子序列，那么来看，如果求最长的上升序列，那么按照贪心，应该最可能的让该序列的元素整体变小，以便可以加入更多的元素。 现在开辟一个新的数组，arr[ 10 ]， { …….} –> 这个是他的空间 ，现在开始模拟贪心算法求解最长上升子序列，第一个数是4，先加进去，那么为{ 4 }再来看下一个数2，它比4小，所以如果他与4替换是不是可以让目前子序列（他这一个元素组成的子序列）变得更小，更方便以后元素的加入呢？是的 。同时还保证了序列的长度不变，所以将大的数替换成小的是可以在保证序列长度不变的前提下是整体序列更小，更容易加入元素 。所以现在为{ 2 } 再来看他的下一个元素3，他要比2大，所以呢加在他的后面，{ 2, 3} 再看下一个元素是1，它比3要小，所以呢为了保证子序列整体尽可能的小（以便可以加入更多的元素），从目前的序列中查找出第一个比他大的数替换掉，那么就变成了{ 1， 3}，继续。。 下一个数是2，那么序列变为{ 1，2}，再下一个数为3，那么序列为{1，2，3}，在下一个数为5，那么序列为{1，2，3，5}，完。 目前序列里又4个元素，所以他的最长子序列的个数为4，但是这个序列是一个伪序列，里面的元素，并不是真正的最长上升子序列，而仅仅和最长上升子序列的个数一样。因为查找的时候用的二分查找，所以时间复杂度为o（nlogn）。
实现代码：
#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]);
/* 求解最长子序列的个数的核心代码 */
/* ********************************************** */
int k = 1;
dp[k] = arr[1];
for(int i = 2; i <= n; i++){
if(dp[k] < arr[i]) dp[++k] = arr[i]; //如果比最后一个元素大，那么就添加再最后末尾处
else *(lower_bound(dp + 1, dp + 1 + k, arr[i])) = arr[i]; //如果比最后一个元素小，那么就替换该序列第一个比他大的数；
}
/* ********************************************** */
printf("最长子序列的个数为： %d", k);
return 0;
}标记路径：
O( )算法标记路径，只需要使用一个记录前驱的数组 pre 即可。
还是用刚才的序列：（7， 9， 6， 10， 7， 1， 3）分别为 （a1, a2, a3, a4, a5, a6, a7）
最开始a1 = 7, 令dp[ 1 ] = 1, pre[1] = 1； 然后看下一个元素 a2 = 9, 令dp[ 2 ] = 1, pre[2] = 2, 那么需要检查 i 前面是否有比他小的 因为 a1 < a2 而且 dp[ 1 ] + 1 > dp[ 2 ], 所以dp[ 2 ] = dp[ 1 ] + 1 == 2，同时更新标记 pre[2] = 1; 然后再看下一个元素 a3 = 6, 令 dp[ 3 ] = 1, pre[3] = 3, 那么需要检查前面的元素 a1 与 a2 是否有比他小的， 一看没有，辣么 到目前为止，子序列就是他自己。 然后再看一下下一个元素 a4 = 10; 令 dp[ 4 ] = 1, pre[4] = 4; 那么需要依次检查前面的元素 a1 与 a2 与 a3 是否有比他小的 , 一看a1比它小，而且呢，dp[ 1 ] + 1 > dp[ 4 ] 所以呢 dp[ 4 ] = dp[ 1 ] + 1 == 2, pre[4] = 1, 说明此时 a1 与 a4 可以构成一个长度为 2 的上升子序列，再来看看还可不可以构成更长的子序列呢，所以咱们再来看看 a2 , a2 < a4 而且呢 dp[ 2 ] + 1 == 3 > dp[ 4 ] == 2 所以呢dp[ 4 ] = dp[ 2 ] + 1 == 3, pre[4] = 2, 即将a4承接在a2后面比承接在a1后更好，承接在a2后面的序列为：a1 a2 a4 ，构成一个长度为 3 的上升子序列; 然后再来看 a3 , a3 < a4 但是可惜的是 d[ 3 ] + 1 == 2 < dp[ 4 ] == 3 , 所以呢就不能把a4加在a3的后面 。 然后就是重复上述过程，更新完所有的pre。
dp 1 2 1 3 2 1 2 pre 1 1 3 2 3 6 6
最大的 dp 值为 3，所以最长子序列长度为3, 末尾的元素在4位置。 追踪其路径为：4 -> pre[4] == 2 -> pre[2] == 1 -> pre[1] == 1(停止) 路径为 4，2，1，这个为倒叙的，因为从后往前找的。
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1160 一种经典的LIS路径标记的题目。
题意：给出n只老鼠 。每只老鼠有对应的weight 和 speed。现在需要从这 n 只老鼠的序列中，找出最长的一条序列，满足老鼠的weight严格递增，speed严格递减，数据中可能有 weight 和 speed 都相同的老鼠。
题解：我们先按照 speed 递减排序，剩下的只需要找 weight 的严格递增的子序列就可以，这么就转化为求最长上升子序列的问题了。
#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; // 初始化，自己一个元素作为子序列，那么自己的前驱节点就是自己了
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. 满足w的单调严格递增 2. 可以更新 3.由于速度是严格单调递减的，所以加上 dp[j].v != d[i].v 这个条件
{
dp[i] = dp[j] + 1; // 当前的序列是 ai 承接在 aj 之后，所以 ai 的前驱节点是 j 节点
pre[i] = j; // 更改前驱节点
}
if(ans < dp[i]) // 更新记录的最长子序列的长度，以及最长子序列末尾元素的位置
{
ans = dp[i]; // 更新记录的最长子序列的长度
loc = i; // 更新最长子序列末尾元素的位置，为了方便输出路径
}
}
}
for(int i = 1; i <= ans; i++)
{
path[i] = a[loc].id; // 需要记录原来的真实位置，所以给path赋的是 id, 不是loc
loc = pre[loc]; // 根据记录的前驱数组来查找
}// 这里的路径是从后往前的，输出的时候注意需要反过来
printf("%d\n", ans);
for(int i = ans; i >= 1; i--)
{
printf("%d\n", path[i]);
}
return 0;
}nlogn 算法的路径标记： 首先要明确的是通过nlogn算法得到的最后的序列是乱的，只有序列的长度是有价值的，所以最后的序列并不是路径。不过我们可以对更新过程中的实际位置来进行标记，最后得到想要的路径。直接举例子吧。用mp数组记录在序列中的位置。
比如说（4, 2, 3, 1, 2，3，5）这个序列，求他的最长上升子序列，那么来看，如果求最长的上升序列，那么按照贪心，应该最可能的让该序列的元素整体变小，以便可以加入更多的元素。 现在开辟一个新的数组，arr[ 10 ]， { …….} –> 这个是他的空间 ，现在开始模拟贪心算法求解最长上升子序列，第一个数是4，先加进去，那么为{ 4 }，并且这时候 mp[1] = 1，因为a1在序列中是在第一个位置，所以mp[1] = 1。再来看下一个数2，它比4小，所以如果他与4替换是不是可以让目前子序列（他这一个元素组成的子序列）变得更小，更方便以后元素的加入呢？是的。所以现在为{ 2 } 并且这时候 mp[2] = 1，因为a2在序列中仍然是在第一个位置，所以mp[2] = 1。再来看他的下一个元素3，他要比2大，所以呢加在他的后面，{ 2, 3} 并且这时候 mp[3] = 2，因为a2在序列中是在第2个位置，所以mp[3] = 2。 再看下一个元素是1，它比3要小，所以呢为了保证子序列整体尽可能的小（以便可以加入更多的元素），从目前的序列中查找出第一个比他大的数替换掉，那么就变成了{ 1， 3} 并且这时候 mp[4] = 1，因为a4在序列中是在第一个位置，所以mp[4] = 1，继续。下一个数是2，那么序列变为{ 1，2}并且这时候 mp[5] = 2，因为a5在序列中是在第2个位置，所以mp[5] = 2，再下一个数为3，那么序列为{1，2，3}并且这时候 mp[6] = 3，因为a6在序列中是在第3个位置，所以mp[6] = 3，在下一个数为5，那么序列为{1，2，3，5}并且这时候 mp[7] = 4，因为a7在序列中是在第4个位置，所以mp[7] = 4，完。 目前序列里又4个元素，所以他的最长子序列的个数为4，但是这个序列是一个伪序列，里面的元素，并不是真正的最长上升子序列，而仅仅和最长上升子序列的个数一样。因为查找的时候用的二分查找，所以时间复杂度为o（nlogn）。
序列 ： 4, 2, 3, 1, 2, 3, 5 mp: 1 1 2 1 2 3 4
// 所以从最右边往左边找即可：
for(int i = n; i >= 1; i--)
{
if(mp[i] == top) // top 是最长子序列的长度
path[top--] = i; // path 记录的路径
}
// 在这里路径为： 4 5 6 7题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1160 和上面的例题一样只是做法用的 nlogn 的算法。
#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; // 将第一个元素压入栈中
mp[a[1].id] = 1; // 确定第一个元素的位置
for(int i = 2; i <= len; ++i)
{
if(a[i].w > st[top]) // 如果当前的值大于栈顶的元素
{
st[++top] = a[i].w; // 加入栈中
mp[a[i].id] = top; // 标记在栈中的实际位置，方便后续查找路径
}
else
{
int l = 1, r = top; // 二分查找第一个比 a[i].w 大的元素，来进行替换
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; // 替换
mp[a[i].id] = l; // 记录实际位置在栈中的
}
}
ans = top;
for(int i = len; i >= 1; i--)
{
if(mp[a[i].id] == top) //根据位置来找出路径
path[top--] = a[i].id;
}
printf("%d\n", ans);
for(int i = 1; i <= ans; i++)
{
printf("%d\n", path[i]);
}
return 0;
}发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/130480.html原文链接：https://javaforall.cn
腾讯云开发者
