Pascal经典算法详解 – 最长递增子序列

Pascal经典算法详解 – 最长递增子序列 给定数列A1,A2,…An，求最长递增子序列输入： 第一行一个整数n，表示有n个数(n<=1000) 第二行n个整数，用空格隔开。输出： 最长递增子序列长度。

【分析】&nbsp&nbsp&nbsp&nbsp&nbsp在求以Ai为末元素的最长递增子序列时，找到所有序号在Ai前面且小于Ai的元素Aj，即j&nbsp&nbsp&nbsp&nbsp阶段i:以第i个数为末元素&nbsp&nbsp&nbsp&nbsp状态S[i]:以第i个数为末元素的可能递增序列长度&nbsp&nbsp&nbsp&nbsp转移方程：S[i+1]←max{S[i]}+1【算法】

    S[1]:=1;                   {以第一个元素为末元素的递增序列长度肯定是1}
    For i←2 to n do
      For j←1 to i-1 do
        Begin
          搜索A[i]前面比A[i]小的数A[j]，得到对应的S[j];
          S[i]←max{S[j]}+1;
        End;
    Write(max{S[i]});

参考程序

Program dizeng;
const
  max=1000;
var
  i,j,n,t,maxs:longint;
  a,s:array[1..max] of longint;
begin
  readln(n);
  for i:=1 to n do
    read(a[i]);
  s[1]:=1;
  for i:=2 to n do
   begin
    maxs:=0;
    for j:=1 to i-1 do
      if a[j]<a[i] then if maxs<s[j] then maxs:=s[j];
    s[i]:=maxs+1;
   end;
  maxs:=0;
  for i:=1 to n do
    if maxs<s[i] then maxs:=s[i];
  write(maxs);
end.