AcWing 3311. 最长算术
原题链接
简单
作者:
不幸到吃土
,
2025-01-04 22:41:30
,
所有人可见
,
阅读 1
//求相同公差的连续数列,故联想到差分数列 → 转化为:在差分数列中,求最长且连续相同的序列
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 200010;
int a[N];
int b[N]; //用于构造差分数列
int main(){
int T;
cin >> T;
for(int cases = 1; cases <=T;cases++){
int n;
cin >> n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i] = a[i] - a[i-1];
}
b[1] = 0;
int ans = 0;
for(int i=1,j=1;i<=n;i++){ //i指向左端点,j指向右端点
j = i;
while(j <= n && b[j] == b[j+1])
j++;
ans = max(ans,j-i+2); //例: 9 7 5 3 → 对应差分数列: 9 -2 -2 -2 故若有≥2的相同差分,必然有+1个的长度,即:(i - j + 1) + 1
i = j;
}
printf("Case #%d: %d\n",cases, ans);
}
return 0;
}