线性DP：最长上升子序列（子序列可不连续，子数组必须连续）

 

目录

 

Q1：简单遍历

Q2：变式（加大数据量）

---

Q1：简单遍历

Dp问题	状态表示 f(i,j)	集合	所有以第i个数结尾的上升子序列集合
			-
		f(i,j)的值存的是什么	序列长度最大值max
			-
	状态计算 （其实质是集合的划分）	划分	f[ i ] = max(f[ i ] , f [ j ]+1), j < i ,a[ j ]<a[ i ] 以上面的条件作为选或不选聚类形成划分依据

#include<iostream>
#include<algorithm>
using namespace std;const int N=1010;int n;
int a[N], f[N];int main()
{cin>>n;for (int i = 1; i <= n; i++) cin>>a[i];for (int i = 1; i <= n; i++){f[i] = 1;  //初始化，只有a[i]一个数for (int j = 1; j < i; j++)//j<i,a[j] < a[i]，max三个条件作为集合划分为选或不选的依据if (a[j] < a[i])f[i] = max(f[i], f[j] + 1);}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i]);//在dp数组内找maxcout<<res;return 0;
}

Q2：变式（加大数据量）

最终的逻辑上的候选最长子序列中越靠前的数字越小越好

 比如说3 8和1 8,1 8组合更好， 因为1和8之间的差距大，可以插入作为序列长度的数字多，所以在dp数组中可以不记录3 8这个序列，把这一部分冗余去除。

那么换成与上述状态表示的集合“所有以第i个数结尾的上升子序列集合”的逻辑来讲，相同长度最后结尾的数字越小越好。

需要存储：所有长度对应的最小结尾值，定义一个q[N]数组

 

上图自变量是长度，应变量是该序列对应最小结尾值

可以证明是该数组是单调递增的，因为假设长度为5的序列最小结尾值为10，长度为6的序列最小结尾值为8，那我是不是其实可以把长度为5的序列的10去掉换为8，把长度为6的序列的8去掉换为10啊？所以这种情况如果说代码逻辑存的对的话是不应该发生的，故严格递增。

核心过程：在q数组中找小于a[i]的最大的一个数，我们在逻辑上是为了将a[i]插入到该逻辑子序列（候选的最长上升子序列，是我们的目标但是我们不存它的全部，只在q对应长度下标位置存它的最后一位数）的结尾，而q数组正好是存储的该子序列结尾元素，所以最后实际的操作就是“覆盖”掉q数组该位置的元素， 以实现逻辑上的逻辑子序列的后插操作。同样也不用担心“重复覆盖”问题，比如q[1]是否被覆盖两次以上从而造成逻辑子序列逻辑长度与q下标不对应的情况，因为我们在小于a[i]、最大这里对我们找的q下标位置做了确切的定位，只要在q中存在元素比q[1]大的元素q[j]或者边界位置空白，那么a[i]就会跳过q[1]被放在q[j]位置或者右边界处。

#include<iostream>
#include<algorithm>
using namespace std;const int N=100010;
int a[N],q[N];//a存输入进来的数，q每个数组元素位置i的意义为序列长度为i的序列结尾的最小值
int n;int main()
{cin>>n;for(int i=0;i<n;i++)cin>>a[i];int len=0;//q中的元素个数q[0]=-2e9;//哨兵for (int i = 0; i < n; i++){int l=0,r=len;while (l < r)//二分过程，在q中找小于a[i]的最大的一个数{int mid = l + r + 1 >> 1;//+1是为了边界 if (q[mid] < a[i]) l = mid;else r = mid - 1;}len = max(len, r + 1);q[r + 1] = a[i];//不用担心覆盖问题，找到了就该覆盖，在逻辑上是个后插操作//逻辑上在招的对应上升子序列后插，存储上是结尾数字，那就是要赋值给q[r + 1]}cout<<len;return 0;
}