最长的不下降子序列n log n.ppt

最长不下降子序列 O(NlogN)算法 ——by yl O(N ) 先看普通思路 for i:=1 to n do begin f[i]:=1; for j:=1 to i-1 do if(a[j]=a[i])and(f[j]+1f[i]) then f[i]:=f[j]+1; ans:=max(ans,f[i]); end; 2 先来说一说思路： 在枚举i时，找到在i之前的一个数j 使得a[j]=a[i] 并且使f[j]+1最大 O(N ) 2 换一种思路 设t[i]为 在数值为i的数中(以i结尾的) 最长的一段不下降子序列的长度 那么t[i]=max{f[j]}(a[j]=i) 所以对于一个i 可以快速知道f[i] 即 f[i]=max(t[j])+1 (1=j=a[i]) 换一种思路 那么我们可以得到以下程序 for i:=1 to n do begin for j:=1 to a[i] do if(t[j]+1f[i]) then f[i]:=t[j]+1; t[a[i]]:=max(t[a[i]],f[i])//更新 ans:=max(ans,f[i]); end; 看出这个程序仍然是O(N )的！ 2 优化 在这个程序当中，我们可以看出 查询是O(N)的，而更新则是O(1)的 有平衡一点的方法吗？ 树状数组！ 优化 我们可以看出每次查找的只是1~a[i]的数 更新只更新一个数 更新的这个数对(a[i]~maxn)都有影响 我们可以用树状数组优化这两个操作 优化 for i:=1 to n do begin f[i]:=find(a[i])+1; //查找a[i]之前的最大数 change(a[i],f[i]); //更改a[i]以后的数 end. 优化 change(x,data) while(xMaxn)do begin if(datat[x]) then t[x]:=data; inc(x,x and -x); end; find(x) ret:=0; while(x0)do begin if(t[x]ret) then ret:=t[x]; dec(x,x and -x); end;