题目描述

一个算术数组是指至少包含两个整数，且相邻整数之间的差值都相等的整数数组。

例如，[9、10]，[3、3、3] 和 [9、7、5、3] 是算术数组，而 [1、3、3、7]，[2、1、2]，和 [1、2、4] 不是算术数组。

Sarasvati 有一个包含 N 个非负整数的数组，其中的第 i 个整数为 Ai。

她想从数组中选择一个最大长度的连续算术子数组。

请帮助她确定最长的连续算术子数组的长度。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N。

第二行包含 N 个整数，其中第 i 个整数表示 Ai。

输出格式
每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x 为组别编号（从 1 开始），y 表示最长的连续算术子数组的长度。

数据范围
1≤T≤100,
1≤Ai≤109,
对于每个测试点，满足 2≤N≤2×105 的数据一定不超过 10 组，其余数据则满足 2≤N≤2000。

样例

输入样例

4
7
10 7 4 6 8 10 11
4
9 7 5 3
9
5 5 4 5 5 5 4 5 6
10
5 4 3 2 1 2 3 4 5 6

输出样例

Case #1: 4
Case #2: 4
Case #3: 3
Case #4: 6

样例解释
对于测试数据 1，最长的连续算术子数组为 [4,6,8,10]。

对于测试数据 2，最长的连续算术子数组就是数组本身。

对于测试数据 3，最长的连续算术子数组为 [4,5,6] 和 [5,5,5]。

对于测试数据 4，最长的连续算术子数组为 [1,2,3,4,5,6]

算法分析

要求最长连续子算术数组
这里采用DP来做
按照闫氏DP分析法

状态表示：
f[i] : 以第i个数结尾的最长连续子算术数组

状态计算 ：
f[i] = f[i-1] + 1 (如果第i个数可加在f[i-1]后，即满足s[i] - s[i-1] == s[i-1) - s[i-2])
否则f[i] = 2(因为题目给定N >= 2,所以对任何数组，满足要求的至少为2个 ： s[i]、s[i-1])

时间复杂度

O(TN)

C 代码

#include<stdio.h>
int T,n,s[200010];
int f[200010];

int max(int a,int b)
{
    if(a >= b) return a;
    else return b;
}

int main()
{
    scanf("%d",&T);
    for(int j = 1;j <= T;j++)
    {
        scanf("%d",&n);
        for(int i = 1;i <= n;i++) scanf("%d",&s[i]);
        f[2] = 2;
        int res = 0;
        for(int i = 3;i <= n;i++)
        {
            if(s[i] - s[i-1] == s[i-1] - s[i-2]) f[i] = f[i-1] + 1;
            else f[i] = 2;
            res = max(res,f[i]);
        }
        printf("Case #%d: %d\n",j,res);
    }
    return 0;
}