最长上升子序列

var
a,f{DP记录},p{后面的}:array[1..1000]of longint;
i,j,k,n:longint;
begin
readln(n);
for i:=1 to n do
begin
read(a[i]);
f[i]:=1;{预处理}
end;
for i:=n-1 downto 1 do
for j:=n downto i+1 do
if (a[i]<a[j])and(f[i]<=f[j])
then begin
p[i]:=j;
f[i]:=f[j]+1;
end;
k:=0;
for i:=n downto 1 do
if f[i]>j
then begin
j:=f[i];
k:=i;
end;
writeln(j);
while k<>0 do
begin
write(k,' ');
k:=p[k];
end;
end.
这是n2的算法,大牛会写nlog(n)的算法,就是用堆来优化
这我听过但忘了

最长上升子序列问题是各类信息学竞赛中的常见题型，也常常用来做介绍动态规划算法的引例，笔者接下来将会对POJ上出现过的这类题目做一个总结，并介绍解决LIS问题的两个常用
算法(n^2)和(nlogn).
问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列（设为s1,s2,...sn），使得这个子序列满足这样的性质，s1<s2<s3<...<sn并且这个子序列的长度最长。输出这个最长的长度。（为了简化该类问题，我们将诸如最长下降子序列及最长不上升子序列等问题都看成同一个问题，其实仔细思考就会发现，这其实只是<符号定义上的问题，并不影响问题的实质）
例如有一个序列:1 7 3 5 9 4 8,它的最长上升子序列就是