这题就没得暴力前缀和了(老老实实打DP)
输入样例
7
1 7 3 5 9 4 8
输出样例
4
解题思路
1.找子问题
“求序列的前n个元素的最长上升子序列的长度”是个子问题,但这样分解子问题,不具有“无后效性”,因为假设F(n) = x,但可能有多个序列满足F(n) = x。有的序列的最后一个元素比 an+1小,则加上an+1就能形成更长上 升子序列;有的序列最后一个元素不比an+1小……以后的事情受如何达到状态n的影响,不符合“无后效性” ,因此我们必须换一种思路来解决此问题。
“求以ak(k=1, 2, 3…N)为终点的最长上升子序列的长度”,一个上升子序列中最右边的那个数,称为该子序列的 “终点”。虽然这个子问题和原问题形式上并不完全一样,但是只要这N个子问题都解决了,那么这N个子问题的解中, 最大的那个就是整个问题的解。
2.确定状态
子问题只和一个变量—— 数字的位置相关。因此序列中数的位置k就是“状态”,而状态 k 对应的“值”,就是以ak做为“终点”的最长上升子序列的长度。 状态一共有N个。
3.找出状态转移方程
maxLen (k)表示以ak做为“终点”的
最长上升子序列的长度那么:
初始状态:maxLen (1) = 1
maxLen (k) = max { maxLen (i):1<=i < k 且 ai < ak且 k≠1 } + 1 若找不到这样的i,则maxLen(k) = 1
maxLen(k)的值,就是在ak左边,“终点”数值小于ak ,且长度最大的那个上升子序列的长度再加1。因为ak左边任何“终点”小于ak的子序列,加上ak后就能形成一个更长的上升子序列。
有了这个思路,我们就可以很轻松地写出代码了。然而,即使到了这里,我们依然还能从两个方向解决这道题
N^2 or N log N
N^2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read () { LL res = 0 ;int f (1) ;char ch = getchar ();
while (!isdigit(ch)) { if (ch == '-') f = -1 ;ch = getchar();}
while (isdigit(ch)) res = (res << 1) + (res << 3) + (ch ^ 48) ,ch = getchar(); return res * f ;
}
const int MAXN=1000000;
int n;
int a[MAXN];
int maxLen[MAXN];
int main() {
n=read();
for(register int i = 1; i <= n; i++) a[i]=read(),maxLen[i] = 1;
for(register int i = 1; i <= n; i++)
for(register int j = i + 1; j <= n; j++)
if( a[j] > a[i] ) maxLen[j] = max(maxLen[j],maxLen[i]+1);
cout << * max_element(maxLen+1,maxLen + n + 1 ) << endl ;
return 0;
}
妥妥的超时了两个点
80分的好分数
怎么办呢...优化鸭
那么问题来了 该怎么去优化
看这个语句
if( a[j] > a[i] ) maxLen[j] = max(maxLen[j],maxLen[i]+1);
你能否想到二分。。 这样就可以弄到n log n的算法
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL read() { LL x=0; int f=1; char ch=getchar();
while(!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x*f;
}
LL n;
LL len=1;
const int N=1<<20;
int a[N],d[N];
signed main(){
n=read(); for(register int i=1; i<=n; i++) a[i]=read();
d[1]=a[1];
for(register int i=2; i<=n; i++) {
if(a[i]>d[len]) d[++len]=a[i];
else d[lower_bound(d+1,d+len+1,a[i])-d]=a[i];
}
cout << len << endl ;
return 0;
}