<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $

题目描述

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

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

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

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

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

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

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

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

输出格式

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

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

数据范围

$1 \\le T \\le 100$,
$1 \\le A_i \\le 10^9$,
对于每个测试点，满足 $2 \\le N \\le 2 \\times 10^5$ 的数据一定不超过 $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, 动态规划) $O(n)$

设 $f[i]$ 为以 $a[i]$ 结尾的最长的连续算术子数组的长度。
状态转移方程：$f[i]=\begin{cases} f[i-1]+1\qquad\qquad i\ge 2\ \text{and}\ a[i]-a[i-1]=a[i-1]-a[i-2]\\\ \qquad 1\qquad\qquad\qquad\ i=0\\\ \qquad 2\qquad\qquad\qquad\ \text{otherwise} \end{cases}$

时间复杂度

由于 $f[i]$ 只和 $f[i-1]$ 相关，所以可以在 $O(n)$ 的时间复杂度内推出答案

空间复杂度

这个算法只需要存 $a$ 数组和 $f$ 数组，而这两个数组大小都是 $O(n)$ 的，所以空间复杂度就是 $O(n)$。

C++ 代码

#include <iostream>

using namespace std;

const int N = 200010;

int t, n; // t, n: 如题意
int a[N], f[N]; // a: 如题意, f[i]: 以 a[i] 结尾的最长的连续算术子数组的长度

int main()
{
    cin >> t;
    for (int c = 1; c <= t; c ++ ) // c: 组别编号
    {
        cin >> n;
        for (int i = 0; i < n; i ++ ) cin >> a[i];

        int maxv = 2; // 最长的连续算术子数组的长度
        f[0] = 1; // 以 a[0] 结尾的最长的连续算术子数组的长度肯定是 1, 但是这一行不加也可以, 不过加了会更严谨一些
        for (int i = 1; i < n; i ++ )
        {
            if (i > 1 && a[i - 1] - a[i - 2] == a[i] - a[i - 1]) f[i] = f[i - 1] + 1; // 如果 a[i - 2], a[i - 1], a[i] 构成连续算术子数组，则以 a[i] 结尾的最长的连续算术子数组的长度是以 a[i - 1] 结尾的最长的连续算术子数组的长度 + 1
            else f[i] = 2;
            maxv = max(maxv, f[i]); // 边算边更新答案
        }

        printf("Case #%d: %d\n", c, maxv); // 节省码长，用 printf
    }

    return 0;
}