算法学习之寻找最长等差数列

               int i,j,k,len = 0
               for(i = 0; i < n; i++)
                     for(j = i+1; j < n; j++)
                    {
                        int delta = a[j] - a[i];
                        len = 2;
                        int tmp = a[j];
                        for(k = j+1; k < n; k++)
                       {
                            if(a[k] - tmp== delta)
                          {
                               len++;
                               tmp = a[k];
                          }
                       }
                      求出最大的len
                    }

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct result
{
    int max_len;
    int i;
    int j;
};
int max(int a,int b)
{
    return a > b ? a : b;
}
void find_llap(int *arry,int n)
{
    int dp[50][50]; //dp[i][j]代表以arry[i]和arry[j]为头两个元素的等差数列,此题规模小，规模大的时候i,j可以做hash，就可以节省空间
    int i,j,k;
    struct result result;
    memset(dp,0,sizeof(dp));
    for(i = 0; i < n; i++)
    {
       dp[i][n] = 2; //因为以arry[n]为第二个元素的等差数列长度一定为2
    }
    if(n < 2)
    {
        for(i = 0; i < 2; i++)
            printf("%d ",arry[i]);
        return;
    }
    result.max_len = 0;
    for(j = n-1; j >= 1; j--)
    {
        i = j-1;k = j+1;
        while(i >= 0 && k <= n)
        {
            if(arry[i]+arry[k] > arry[j]<<1) //如果和ai+ak>2aj,说明ak-aj>aj-ai,这个构造不成等差数列,则k以后的更不行，因为数组是升序
             {
                 dp[i][j] = 2;                //所以此步骤直接赋值为2，及只有ai aj构造成等差数列
                 i--;
             }
            else if(arry[i]+arry[k] < arry[j]<<1)
            {
                k++;       //如果ai+ak<2aj,说明ak-aj<aj-ai,所以以ai aj开头的等差数列，往后遍历，可能还有新的元素符合公差，所以k++
            }
            else
            {
                /*如果ai+ak=2aj,则正好构成等差数列，直接将前一个子问题的解+1即可*/
                dp[i][j] = dp[j][k]+1;
                result.max_len = max(result.max_len,dp[i][j]);
                if(result.max_len == dp[i][j])
                {
                    result.i = i;
                    result.j = j;
                }
                i--;k++;
            }
         }
         if(result.max_len == 0)
         {
             result.max_len = 2;
             result.i = 0;
             result.j = 1;
         }
         while(i >= 0) /*这个循环是因为k已经到最后了，所以以这个j为第二个元素的所有数列都是2*/
         {
             dp[i][j] = 2;
             i--;
         }
     }
     int delta = arry[result.j] - arry[result.i];
     int last  = arry[result.i]+(result.max_len-1)*delta;
     for(i = arry[result.i]; i <= last; i+=delta)
        printf("%d ",i);

}

int main()
{
    int n；
    int arry[100];
    scanf("%d",&n);
    int i;
    for(i = 0; i < n; i++)
      scanf("%d",&arry[i]);
    find_llap(arry,n-1);
    return 0；
}