本题需要计算最长的连续等差数列的长度
我们可以转化为差分数组 最长连续相等的长度 最后在加1即可
注意差分数组第一项 我们要设置为0 因为我们差分数组的含义在本题是该项与前一项的差
因为第一项没有前一项 我们就不能将其设置为a[1]
例如
原数组 $10$ $7$ $4$ $6$ $8$ $10$ $11$
差分数组 $0$ $-3$ $-3$ $2$ $2$ $2$ $1$
我们可以看出差分数组最长有三个$2$相连 表示有相邻的三个数与前一个数的差都是2
所以对应的原数组就是 4 6 8 10 (表达不清楚 还请见谅)
记得差分数组找到最长连续的长度后要加一
c++ 代码
#include<iostream>
using namespace std;
const int N=2e5+5;
int T,n,a[N],d[N];
int main(){
cin>>T;
for(int t=1;t<=T;t++){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
d[i]=a[i]-a[i-1];//记录差分哦
}
d[1]=0;//第一项设置为0
int ans=0,l=1,r=1;
while(r<=n){//找相邻且相同的最长序列
if(d[r]!=d[l]){
ans=max(ans,r-l+1);
l=r;
}
r++;
}
ans=max(ans,r-l+1);
printf("Case #%d: %d\n",t,ans);
}
return 0;
}
无数组版本
因为我们只用考虑相邻两项的差
根据上面的思路我们只需要记录a[i-1]-a[i-2]
的值是否与a[i]-a[i-1]
相同即可
我们用d=a[i-1]-a[i]
$l$的含义和上面一样指向差分数组相同元素的最左边的位置
$x$为当前元素值 $y$为上一个元素的值 为了计算a[i]-a[i-1]
#include<iostream>
using namespace std;
int T,n;
int main(){
cin>>T;
for(int t=1;t<=T;t++){
cin>>n;
int l=1,d=0,ans=2,y,x;
for(int r=1;r<=n;r++){
scanf("%d",&x);
if(r==1)y=x;
else if(x-y!=d)ans=max(ans,r-l+1),l=r;
d=x-y,y=x;
}
ans=max(ans,(n+1)-l+1);
printf("Case #%d: %d\n",t,ans);
}
return 0;
}
请问为什么空间复杂度为$O(1)$ ??
下面不是有个无数组版本嘛 那个就是空间复杂度O(1)呀
抱歉,没看到下面就发问了。。
好思路!
ans初始值赋2就不会有问题了
牛逼
错了
hack数据
2
1 2
我有点疑惑 题目中也没有给表面自己是自己的一个子数组
不过数据加强了 我发现了一个错误 就是需要d[1]=0 而不是d[1]=a[1]
例如 对于 2 4 6 8 12
差分数组应该为 0 2 2 2 4 相邻三个2 再加1 才可以表示一个长度为4的等差数列
刚好也把
2
1 2的数据给过了
万分感谢!
女少口阝可
差分好思路
tql,思路秒啊,转成差分
谢谢~ 突发奇想 哈哈哈
确实妙,bi=ai-ai-1,刚刚好是相邻两项的差
这题就很巧妙 不过其他大佬的dp也很厉害