LIS 最长上升子序列

动态规划本质

Future never has to do with past time ,but present does. 现在决定未来，未来与过去无关。

注意本题中的LIS是严格单增（不能重复）

朴素做法 $O(n^2)$

对于每一个元素来说，最长上升子序列就是其本身。
那我们就可以定义一个dp数组 状态设计为，$dp[i]$ 表示以第i元素为结尾的最长上升子序列长度。

至于转移过程，我们可以对于每一个$i$，枚举在$i$之前的每一个元素$j$，然后对于每一个$dp[j]$,如果元素$i$大于元素$j$，那么就可以考虑继承，而最优解的得出则是依靠对于每一个继承而来的dp值，取$max$。

#include<bits/stdc++.h>
const int MAXN=1e5+7;
using namespace std;
int n,a[MAXN], d[MAXN];
int dp() {
	d[1] = 1;
	int ans = 1;
	for (int i = 2; i <= n; i++) {
		d[i] = 1;
		for (int j = 1; j < i; j++)
			if (a[j] < a[i]) {
				d[i] = max(d[i], d[j] + 1);
				ans = max(ans, d[i]);
			}
	}
	return ans;
}
int main() {
	cin>>n;
	for(int i=1; i<=n; i++)
		cin>>a[i];
	cout<<dp()<<'\n';
	return 0;
}

优化做法 $O(nlogn)$

不难看出，对于$O(n^2)$做法而言，其实就是暴力枚举。 那可不可以优化呢?

显然是可以的
我们将原来的dp数组的存储由数值换成该序列中，上升子序列长度为$i$的上升子序列的最小末尾数值。

这个方法极其贪心，但是如果你仔细想，你会发现，他是正确的。

关键操作是每遇到一个新的元素时，就跟已经记录的dp数组当前所记录的最长上升子序列的末尾元素相比较：如果小于此元素，那么就不断向前找，直到找到一个刚好比它大的元素，替换；反之如果大于，么填到末尾元素的下一个。

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+7;
int n,a[N],f[N];
signed main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        f[i]=0x7f7f7f7f;
    }
    f[1]=a[1];
    int len=1;
    for(int i=2; i<=n; i++)
        if(a[i]>f[len])f[++len]=a[i];
        else {
            int pos=lower_bound(f+1,f+len+1,a[i])-f;
            f[pos]=min(a[i],f[pos]);
        }
    cout<<len<<'\n';
    return 0;
}