第1章 最长不下降子序列问题
1.1 最长不下降子序列
【题目描述】最长不下降子序列（LIS）POJ 2533
由n个数组成的序列a[n]，若有下标（又称索引）i1＜i2＜…＜iL，且a[i1]≤a[i2]≤…≤a[iL]，则称存在一个长度为L的不下降序列。
例如序列13,7,9,16,38,24,37,18,44,19,21,22,63,15中，13≤16≤38≤44≤63，所以存在长度为5的不下降子序列。经过观察，还有长度为8的不下降子序列，即7≤9≤16≤18≤ 19≤21≤22≤63。
试编程求最长不下降子序列（又称最长上升子序列，Longest Increasing Sequence，LIS）。
【输入格式】
第1行为n（1≤n≤100 000），表示n个数。第2行为n个数的值。
【输出格式】
一个整数，即最长不下降子序列的长度。
【输入样例】
4
1 3 1 2
【输出样例】
3
【算法分析】
表1.1的第3行表示该序列元素所能连接的最长不下降子序列的长度，因为每个元素本身的长度为1，所以初始时均设为1。第4行表示连接哪个元素以形成不下降子序列。
表1.1
从左向右数第2个元素即7，在它的前面仅有1个元素13，且13＞7，因此无法连成不下降子序列。
第3个元素9的前面有2个元素，其中7＜9，因此7和9可以连成不下降子序列。修改9的序列长度为1+1=2，并修改连接位置为2，即7的序列下标，如表1.2所示。
表1.2
第4个元素16的前面有3个元素，3个元素的值均小于16，因此都可以和16连成不下降子序列。显然将9与16连起来的不下降子序列最优。因为9的序列长度最大，所以修改16的序列长度为2+1=3，并修改连接位置为3，即9的序列下标，如表1.3所示。
表1.3
依次类推，最后的表格应如表1.4所示，其中单元格有底色的数值构成的序列为最长不下降子序列。
表1.4
由表1.4可知，最长不下降子序列的长度为8。如果题目有要求，则还可回溯连接位置，输出最长不下降子序列的每个元素。
根据以上分析，用dp[i]表示前i个元素的最长不下降子序列的长度，得到状态转移方程：
dp[i]=max{dp[j]}+1（其中a[j]≤a[i]且j＜i），时间复杂度为O(n2)。
参考代码如下。注意：该代码无法通过数据规模较大的数据。
1 //最长不下降子序列 —— 朴素算法
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int a[100005],dp[100005];
6
7 int main()
8 {
9 int n,longest=1; //最小长度至少为1
10 scanf("%d",&n);
11 for (int i=1; i<=n; ++i)
12 {
13 scanf("%d",&a[i]);
14 dp[i]=1;
15 }
16 for (int i=2; i<=n; ++i) //从第2个元素开始
17 {
18 for (int j=1; j<i; j++) //比较前面的元素
19 if(a[j]<=a[i] && dp[j]+1>dp[i])
20 dp[i]=dp[j]+1;
21 longest=max(dp[i],longest);
22 }
23 printf("%d\n",longest);
24 return 0;
25 }
在维护一个有序数列时，若要插入一个数x，则可以通过二分查找的方法找到合适的位置后插入该数。根据此方法，可以利用序列的单调性将最长不下降子序列的时间复杂度优化到O(nlogn)。
考虑定义一个数组f[ ]，用于保存长度为i的不下降子序列中的最后一个数。例如序列1,2,4,3，其中有1≤2≤4和1≤2≤3两个长度为3的最长不下降子序列，则f[1]=1，f[2]=2，f[3]=3 （因为由3和4连起来的不下降子序列的长度均为3，且3在4的后面）。但是并不是说数组f[ ]里保存的就一定是最长不下降子序列的元素，例如序列13,7,9,16,38,24,37,18,44,19,21,22,63,15，有一个最长不下降子序列7≤9≤16≤18≤19≤21≤22≤63。最终数组f[ ]里的值如图1.1所示。可以看到，f[3]的值是15，不是16，这是因为后面出现的15覆盖了之前f[3]的值。
图1.1
设longest为当前找到的最长不下降子序列的长度。若插入的数x≥f[longest]，则显然有f[longest+1]=x，longest++；否则在f[1]~f[longest−1]中查找到能连接的最长子序列后，会将x连接到最后（贪心算法思想：将x连接到短的子序列后面不划算）。例如图1.1中，序列中最后一个数15能连接的最长子序列为7,9，长度为2，则f[3]=15。
参考代码如下。
1 //最长不下降子序列 —— 贪心+二分查找算法
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int a[100005],f[100005];
6
7 int main()
8 {
9 int n,longest=0;
10 memset(f,-1,sizeof(f)); //要初始化为-1
11 cin>>n;
12 for(int i=1; i<=n; i++)
13 {
14 cin>>a[i];
15 if(f[longest]<=a[i]) //若插入的数≥f[longest]
16 f[++longest]=a[i]; //将a[i]连接到最后
17 else
18 {
19 int L=0,R=longest;
20 while(L<=R) //二分查找合适的位置
21 {
22 int mid=(L+R)>>1;
23 if(f[mid]<=a[i])
24 {
25 L=mid+1;
26 if(f[L]>a[i])
27 break;
28 }
29 else
30 R=mid-1;
31 }
32 f[L]=a[i]; //保存f[L]值
33 }
34 }
35 cout<<longest<<endl;
36 return 0;
37 }
若需进一步优化代码量，则无须手写二分查找代码，直接使用标准模板库（Standard Template Library，STL）里的upper_bound(a,b,val)函数即可。因为使用该函数能直接二分查找到[a,b]这个有序区间内第1个大于val的值（以指针的形式返回）。
若需要输出最长不下降子序列中的所有元素，则可以定义一个数组，如pos[ ]，用于记录每个元素在最长不下降子序列中的位置。例如表1.5中，longest=8且pos [13]=8，可知a[13] （即63）是最长不下降子序列中的最后一个数；pos[12]=7，可知a[12]（即22）是最长不下降子序列中的倒数第2个数；pos [11]=6，可知a[11]（即21）是最长不下降子序列中的倒数第3个数（虽然pos[9]也等于6，但pos[11]是最后更新的值）；……依据此法一直逆推到最长不下降子序列中的第1个数，再按顺序输出各元素即可。
表1.5
参考代码如下。
1 //最长不下降子序列 — STL二分查找算法
2 #include <bits/stdc++.h>
3 using namespace std;
4
5 int f[100005], pos[100005], a[100005];
6
7 int main()
8 {
9 int n,longest=1;
10 scanf("%d",&n);
11 for(int i=1; i<=n; ++i)
12 scanf("%d", &a[i]);
13 f[1]=a[1];
14 pos[1]=1;
15 for(int i=2; i<=n; ++i)
16 {
17 if(f[longest]<=a[i])
18 {
19 f[++longest]=a[i];
20 pos[i]=longest;
21 }
22 else
23 {
24 int j=upper_bound(f+1,f+longest+1,a[i])-f;//当前地址-首地址=当前下标
25 f[j]=a[i];
26 pos[i]=j;
27 }
28 }
29 printf("%d\n", longest);
30
31 stack <int> st; //以下为输出最长不下降子序列各元素的代码
32 for(int i=n, j=longest; i>=1 && j!=0; --i) //使用堆栈逆序存入最长不下降子序列的元素
33 if(pos[i]==j)
34 {
35 st.push(a[i]);
36 --j;
37 }
38 while(!st.empty()) //顺序输出最长不下降子序列的元素
39 {
40 printf("%d ", st.top());
41 st.pop();
42 }
43 return 0;
44 }