最长不下降子序列

解法

对于c(i)=前i个数中最长不下降子序列的个数，可以这样考虑，除去i不谈，那么之前满足最长下降子序列的c(j)=c(i)-1(因为c(j)在c(i)这个

序列中，它加上i就是i的最长不下降子序列)所以得到状态转移方程。 c(i)=sigma(c(j)) (jai,f(i)=f(j)+1) {sigma就是求和，这里打不出}

观察可能重复的发生情况，对于每一个可能重复的长度为3下降的子序列，它一定是i,j,j(i>j)这种情况，所以可以开一个boolean数组o记录j

是否出现过，若出现了，就不再计算。状态转移方程： c(i)=sigma(c(j)) (j<i,aj>ai,f(i)=f(j)+1，o[j]=false)。

该解法相关资料 http://hi.baidu.com/leokan/blog/item/5056306d01f767f8431694ac.html

pascal代码

program didi; var

 a,b:array[1..1000] of longint;
 i,j,n:longint;

begin

 read(n);
 for i:=1 to n do read(a[i]);
 b[n]:=1;
 for i:=n-1 downto 1 do
   begin
     b[i]:=1;
     for j:=i+1 to n do
       if (a[i]<a[j])and(b[j]>=b[i]) then
       b[i]:=b[j]+1;
   end;
 j:=1;
 for i:=2 to n do
   if b[i]>b[j] then j:=i;
 write(b[j]);

end.