注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!

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

其他 水墨上仙 2109次浏览 已收录 手机上查看

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.


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法详解 – 最长递增子序列
喜欢 (0)
[开心洋葱]
分享 (0)
水墨上仙
关于作者:
水墨上仙
加载中……