等差数列

发布于 2019-04-12  926 次阅读


题目描述

给定n(1<=n<=100)个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.

输入

第一行是一个整数n,接下来一行包括了n个数,每个数的绝对值不超过10000000.

输出

输出你所找出的最长等差数列的长度.

思路

从大到小排序,用三个for来扫描并且保证每一次判断的长度都不一样

const
  maxn=1000;
var
  a:array[1..maxn] of longint;
  i,n,j,k,m,s,ans,x,s1:longint;
  f:boolean;
procedure qsort(l,r:longint);
  var
    i,j,key,temp:longint;
  begin
    if l>=r then exit;
    i:=l;j:=r;
    key:=a[l+random(r-l+1)];
    repeat
      while  (a[i]>key) do inc(i);
      while  (a[j]j;
    qsort(l,j);
    qsort(i,r);
  end;

begin
  readln(n);
  for i:=1 to n do
    read(a[i]);
  randomize;
  qsort(1,n);
   for i := 1 to n-1 do
    for j := i+1 to n do
      begin
        s:=a[j]-a[i];
        x:=2;
        for k:=j+1 to n do
          begin
            if ((a[k]-a[k-1])=s) then
              x:=x+1
            else
              break;
          end;
        if (x>ans) then
          ans:=x;
      end;
    writeln(ans);
end.
]]>