《最长不下降子序列n log n》由会员分享，可在线阅读，更多相关《最长不下降子序列n log n（9页珍藏版）》请在金锄头文库上搜索。
1、最长不下降子序列最长不下降子序列O(NlogN)O(NlogN)算法算法 by ylby ylO(N )O(N )l l先看普通思路先看普通思路l lfor i:=1 to n do beginfor i:=1 to n do beginl lfi:=1;fi:=1;l lfor j:=1 to i-1 do for j:=1 to i-1 do if(ajfi) if(ajfi) then fi:=fj+1;then fi:=fj+1;l lans:=max(ans,fi);ans:=max(ans,fi);l lend;end;2l l先来说一说思路：先来说一说思路：l l在枚举在枚举i
2、i时，找到在时，找到在i i之前的一个数之前的一个数j jl l使得使得ajfi) then fi:=tj+1;if(tj+1fi) then fi:=tj+1;l ltai:=max(tai,fi)/tai:=max(tai,fi)/更新更新 ans:=max(ans,fi);ans:=max(ans,fi);l lend;end;看出这个程序仍然是O(N )的！2优化优化l l在这个程序当中，我们可以看出在这个程序当中，我们可以看出l l查询是查询是O(N)O(N)的，而更新则是的，而更新则是O(1)O(1)的的有平衡一点的方法吗？树状数组！优化优化l l我们可以看出每次查找的只是我们可以
3、看出每次查找的只是1ai1ai的数的数l l更新只更新一个数更新只更新一个数l l更新的这个数对更新的这个数对(aimaxn)(aimaxn)都有影响都有影响l l我们可以用树状数组优化这两个操作我们可以用树状数组优化这两个操作优化优化l lfor i:=1 to n do beginfor i:=1 to n do beginl lfi:=find(ai)+1; /fi:=find(ai)+1; /查找查找aiai之前之前 的最大数的最大数l lchange(ai,fi); /change(ai,fi); /更改更改aiai以后以后 的数的数l lend.end.优化优化l lchange(x,data)change(x,data)l lwhile(xtx) then tx:=data;if(datatx) then tx:=data;l linc(x,x and -x);inc(x,x and -x);l lend;end;l lfind(x)find(x)l lret:=0;ret:=0;l lwhile(x0)do beginwhile(x0)do beginl lif(txret) then ret:=tx;if(txret) then ret:=tx;l ldec(x,x and -x);dec(x,x and -x);l lend;end;
