当前位置:网站首页>最长算术(暑假每日一题 11)
最长算术(暑假每日一题 11)
2022-07-31 11:53:00 【sweetheart7-7】
一个算术数组是指至少包含两个整数,且相邻整数之间的差值都相等的整数数组。
例如, [ 9 、 10 ] , [ 3 、 3 、 3 ] [9、10],[3、3、3] [9、10],[3、3、3] 和 [ 9 、 7 、 5 、 3 ] [9、7、5、3] [9、7、5、3] 是算术数组,而 [ 1 、 3 、 3 、 7 ] [1、3、3、7] [1、3、3、7], [ 2 、 1 、 2 ] [2、1、2] [2、1、2],和 [ 1 、 2 、 4 ] [1、2、4] [1、2、4] 不是算术数组。
Sarasvati 有一个包含 N N N 个非负整数的数组,其中的第 i i i 个整数为 A i A_i Ai。
她想从数组中选择一个最大长度的连续算术子数组。
请帮助她确定最长的连续算术子数组的长度。
输入格式
第一行包含整数 T T T,表示共有 T T T 组测试数据。
每组数据第一行包含整数 N N N。
第二行包含 N N N 个整数,其中第 i i i 个整数表示 A i A_i Ai。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y
,其中 x
为组别编号(从 1 1 1 开始),y
表示最长的连续算术子数组的长度。
数据范围
1 ≤ T ≤ 100 , 1≤T≤100, 1≤T≤100,
1 ≤ A i ≤ 1 0 9 , 1≤A_i≤10^9, 1≤Ai≤109,
对于每个测试点,满足 2 ≤ N ≤ 2 × 1 0 5 2≤N≤2×10^5 2≤N≤2×105 的数据一定不超过 10 10 10 组,其余数据则满足 2 ≤ N ≤ 2000 2≤N≤2000 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]。
#include<iostream>
using namespace std;
const int N = 200010;
int a[N];
int main(){
int t;
scanf("%d", &t);
int n;
for(int k = 1; k <= t; k++){
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
int res = 2;
for(int i = 2; i < n; i++)
if(a[i] - a[i-1] == a[i-1] - a[i-2]){
int j = i + 1;
while(j < n && a[j] - a[j-1] == a[j-1] - a[j-2]) j++;
res = max(res, j - i + 2);
i = j - 1;
}
printf("Case #%d: %d\n", k, res);
}
return 0;
}
边栏推荐
猜你喜欢
随机推荐
想吃菌子,当然是自己上山找了
IDEA configure method annotation automatic parameters
[Virtualization ecological platform] Raspberry Pi installation virtualization platform operation process
Docker安装canal、mysql进行简单测试与实现redis和mysql缓存一致性
mysql automatically adds creation time and update time
三六零与公安部三所发布报告:关基设施保护成为网络安全博弈关键
Different lower_case_table_names settings for server ('1') and data dictionary ('0') solution
【虚拟化生态平台】树莓派安装虚拟化平台操作流程
关于Mysql数据库的介绍
502 bad gateway causes and solutions
The latest MySql installation teaching, very detailed
502 bad gateway原因、解决方法
分布式id解决方案
After Effects 教程,如何在 After Effects 中修复曝光不足的镜头?
Detailed tutorial on distributed transaction Seata
Use jOOQ to write vendor-agnostic SQL with JPA's native query or @Formula.
一周精彩内容分享(第14期)
B/S架构模式的一个整体执行流程
The most complete phpmyadmin vulnerability summary
线程池 ThreadPoolExecutor 详解