题目描述
 给你一个以正整数构成的序列，求它的最长等差子序列的长度(至少为3)
若该序列不存在，则输出No Answer
输入
 两行，第一行，序列中的正整数数目N。
 第二行，N个整数来描述这个序列。
 输出
 一个整数，表示这个序列的最长等差子序列的长度。
 样例
 输入  复制
5
 2 1 4 3 6
输出  
3

如题，其中数据范围是1≤N≤5,000，0≤|序列元素|≤1000

供参考：

#include <stdio.h>
#include <malloc.h>
#define max(x, y)   (x) > (y) ? (x) : (y)
#define N 5001
int maxlength(int* a, int n)
{
    int i, j, m;
    if (n <= 2) return 2;
    if (n == 3)
        return a[2] - a[1] == a[1] - a[0] ? 3 : 2;
    int** dp = (int**)malloc(sizeof(int*) * n);
    for (i = 0; i < n; i++)
        dp[i] = (int*)malloc(sizeof(int) * n);
    for (i = 0; i < n ; ++i) {
        for (j = i + 1; j < n; ++j) {
            dp[i][j] = 2;
        }
    }
    int res = 2;
    for (i = 1; i < n; ++i) {
        for (j = i + 1; j < n; ++j) {
            for (m = 0; m < i; ++m) {
                if (a[j] - a[i] == a[i] - a[m]) {
                    dp[i][j] = max(dp[i][j], dp[m][i] + 1);
                }
            }
            res = max(dp[i][j], res);
        }
    }
    for (i = 0; i < n; i++)
        free(dp[i]);
    free(dp);
    return res; //返回最长等差序列长度
}
int main()
{
    int a[N] = { 0 }, i, max = 0, n;  //{ 2,1,4,3,6 } { 9,4,7,2,10 }
    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    max = maxlength(a, n);
    if (max >= 3)
        printf("%d", max);
    else
        printf("No Answer");
    return 0;
}

[此贴子已经被作者于2022-3-2 08:47编辑过]

leetcode 上有答案及分析