引言

上次我们说了基础的最长上升子序列（看这一篇前可以先看一下最长上升子序列）

这次，我们再说一下如何优化，提高效率

我们先来看一道模板题

题目：

题目描述

输入格式

输出格式

输入样例

3
1 3 2

输出样例

数据范围

想法

应该很容易想到把问题转化为求最大上升子序列，因为这道题是说修改多少个就能变成严格单调递增，其实就是问这个数列中最大上升子序列，除这一个序列外的就是要修改的数字

最原始的代码如下

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;long long a[100001];
int f[100001];
//f[i]表示以第i项结尾的最长上升子序列
int main()
{int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}int maxn = 0;for(int i = 1;i <= n;i++){f[i] = 1;//初值for(int j = 1;j <= i - 1;j++){if(a[j] < a[i])f[i] = max(f[i],f[j] + 1);maxn = max(maxn,f[i]);}}cout << n - maxn;return 0;
}

（如果没有看懂上面这段代码的话建议看一下我的上一篇题解）

如果只这样写的话，会有一个样例错了

想要得到满分，则必须进行优化，下面，我们来详细讲一下最长上升子序列的优化

优化

我们来模拟一下基础版本

上图是原先数组，现在我们要求F[10]（以第10项为结尾（就是7）的最大上升子序列长度）

如上图，很多项都能推第10项

但这样的话会很慢，因为每一项都会有这么多项可以推，枚举起来效率实在低，那怎样才能减少要枚举的次数呢？

其实在这几项中有许多没有枚举意义的项就拿第一项（3），第五项（2），第六项（3）举例

这三项中，F数组值都是1，就是说以它们为结尾的最长上升子序列长度都是1，那么对于第十项（7）我们只选择有最优的。很容易看出来，第五项（2）才是最优的，因为在这三项中，2是数值最小的不管怎么样，都比第一项和第六项（3）强（因为是要得到最长“上升”子序列，当然是前面数越小对后面越好啊），所以对于F数组值为1的，我们只选择2。

那么，我们把这个操作推广，就会得到：对于F数组值相同的几项中我们选择数值最小的，其他的全部忽略。

所以现在需要一个数组g来存储这些“有用”的项。

假设我们已经有数组g了：

（已经按F数组值从小到大排好了）

现在我们就是要找到这四个数中两边数值刚好能“夹住”7的位置

long long a[100001];
int f[100001];
//f[i]表示以第i项结尾的最长上升子序列
int g[100001];
//g[i]表示上升子序列长度为i时，结尾最小值
int sz = 0;//前i-1个最长有多长
int maxn = 0;for(int i = 1;i <= n;i++){int pos = 1;while(pos <= sz && g[pos] < a[i]) pos++;f[i] = pos;g[pos] = a[i];sz = max(sz,pos);maxn = max(maxn,f[i]);}

在代码中，我们用一个pos来实现：首先pos=1初始化，接下来那个while来循环找到位置

循环条件：pos要在这个这个g数组中的某一个位置（就是其中的就是长度要小于等于最大长度，因为g数组也就只有这些数值了）并且还需要有g数组中的第pos个要小于当前这个数a[ i ]

那循环完后就找到pos了，直接将F[ i ]赋值为pos（注意，不是pos+1，因为在循环中，pos最后会多加一个1），那么我们现在要做的就是改变g[pos]

举刚才那个例子就是说把9划掉，换成7，因为7和9的F数组值相同，最小的必定要好

sz = max(sz,pos);

对于这行代码：

因为pos有可能比sz大，（循环中不停+1嘛）所以sz值也就要更新了，如果pos大于sz的话那么就sz=pos赋值，所以就是这行代码。

最后我把最终代码附上来

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;long long a[100001];
int f[100001];
//f[i]表示以第i项结尾的最长上升子序列
int g[100001];
//g[i]表示上升子序列长度为i时，结尾最小值
int sz = 0;//前i-1个最长有多长
int main()
{int n;cin >> n;for(int i = 1;i <= n;i++){cin >> a[i];}int maxn = 0;for(int i = 1;i <= n;i++){int pos = 1;//表示以第i项为结尾的最长上升子序列的长度while(pos <= sz && g[pos] < a[i]) pos++;//找到posf[i] = pos;赋值g[pos] = a[i];//既然刚才循环的倒数第二次g[pos]最后一次<a[i]，所以这时的g[pos]应该是a[i]sz = max(sz,pos);//更新最大长度，pos有可能大于sz，则sz不是最大长度maxn = max(maxn,f[i]);}cout << n - maxn;return 0;
}