最长升
青葱
2019-04-13 17:42:39
# 关于LIS的几种解法
## **一、LIS的朴素做法O($n^2$)**
------------
**f[ i ]:以第i个数为结尾的最长升长度**
**w[ i ]:第i个数的权值**
------------
考虑新加入一个数 j 在原序列后,所有权值小于w[ j ]的数所形成的最长升都能扩展一个位置
换句话说,j 的最长升是从**以比它小且在它左边的数为末尾的最长升**加一个数 j 得到的
------------
### **动态转移方程如下:**
### ***f[ j ]=max{ $\sum_{i=1}^j$ f[ i ] | w[ i ] > w[ j ] }+1***
------------
```cpp
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
if(w[j]<=w[i])
f[i]=max(f[i],f[j]+1);
}
}
```
### **其特点在于:**
#### 1. 简单又暴力的美学
#### 2. 可以求出以每个数为结尾的最长升长度
#### 3. 可以顺手求出最长升原序列
------------
## **二、LIS单调栈做法O($nlog^{}_{2}n$)**
------------
假设这里有一个序列是递增的,我们显然可以很好地求出最长升的长度
而对于非递增的序列,我们也可以通过**维护一个单调栈**来使其递增
------------
### **单调栈一般流程:**
#### 1. 二分找到栈中小于它的第一个数
#### 2. 如果存在,替换它,否则压新数入栈
#### 3. 当前数所在栈中的编号即为以它为结尾的最长升长度
------------
### **单调栈设计思路的由来:**
------------
#### 从第一个数到第 n 个数依次插入序列,分析题目的单调性:
设当前要插入第 j 个数,其权为w[ j ]
------------
1、我们可以轻易的知道,在以第一个数到第 j -1个数为末尾的最长升在位置上是允许被扩展的,第 j 个数可以插入到以它之前所有权值小于w[ j ]的数所形成的最长升后
即:**只要是权值小于等于w[ j ]的数,我们都一视同仁为可扩展数,以其为结尾的最长升,一视同仁为可扩展序列**
------------
2、我们还可以发现,对于一个数的插入是没有后效性的
即:确定了以w[ j ]为结尾的最长升,**无论在它后面插入多少个数,以w[ j ]为结尾的最长升是不变的**
------------
3、于是,我们很自然地想,要确定最长升,就要有最长的可扩展序列
即:如果我们能够知道在第1个数到第 j -1个数所形成的不同长度的最长升中,
**长度最长且结尾数字小于等于w[ j ]的最长升**,即找到了最优扩展位置,就可以求出以第 j 个数为结尾的最长升
4、更秒的是,我们可以证明,更长的上升子序列的结尾数字一定不小于更短的上升子序列(我们可以通过舍弃长的上升子序列的前几个数得到短的上升子序列)
即:**我们维护的这个栈是单调的**,我们可以二分找到最佳扩展位置
------------
### 需要注意的是:
单调栈内在不同位置上的数 即:
#### **在第 j 个数之前不同长度上升子序列的最小结尾数字**
而实际上,**我们维护的单调栈并非维护的一个序列,而是不同长度下结尾数字最小的多个序列**
但是,我们在维护单调栈的同时,改变了位置关系,所以,对于单调栈内维护的序列,只有长度与最小末尾数字是可以确定的
------------
```cpp
for(int i=1;i<=n;i++){
if(b[i]>m[top]) m[++top]=b[i];
else m[lower_bound(m+1,m+top+1,b[i])-m]=b[i];
}
```
------------
### **其特点在于:**
#### 1. 简洁而又睿智的美学
#### 2. 可以求出以每个数为结尾的最长升长度
#### 3. 不能很有效的求出最长升序列
------------
## **三、LIS的DP优化O($nlog^{}_{2}n$)**
基于朴素DP和单调栈的思想:
我们插入到一个数时,仅仅需要知道以比它小的数结尾的最长上升子序列长度
那么我们可以用数据结构维护这个性质
即:**我们需要一种数据结构维护区间最大值和单点插入**
比如:树状数组、线段树
------------
### **一般流程:**
我们以w[ j ]作为下标,以第 j 个数能形成的最长升长度为权值
当插入到第 j +1个数时,只需要询问1~w[ j +1]之间的长度最大值
之后插入第 j +1个数,继续下面的数
------------
```
for(int i=1;i<=n;i++){
int p=_map[read()];
f[i]=query(p)+1;
ans=max(ans,f[i]);
add(p,f[i]);
}
```
答案即为以各个数为结尾的最长升中的最大值
------------
### 需要注意的是:
1、如果我们用:pair<int.int>(第一维维护最大值,第二维维护对应的位置下标),代替最大值的int,**就能够层层向上,找到原序列**
2、因为下标为权值,所以**对于一般题目需要离散化**
------------
### **其特点在于:**
#### 1. 精简而又巧妙的美学
#### 2. 可以求出以每个数为结尾的最长升长度
#### 3. 可以很有效的求出最长升序列