北邮oj289-最长连续等差子数列
动态规划问题
#include<bits/stdc++.h>
using namespace std;
#define maxn 105
int f[maxn];
int dp[maxn];
int main(){
int T,N;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
for(int i=0;i<N;i++){
scanf("%d",&f[i]);
dp[i] = 1;
}
dp[1] = 2;//默认为2
int max;//最长连续等差子数列长度
if(N==1) max = 1;//只有一个元素的特殊情况
else max = 2;
for(int i=2;i<N;i++){//本方法如不随时比较max,max将会被覆盖
if(f[i]-f[i-1]==f[i-1]-f[i-2]){
dp[i] = dp[i-1]+1;//加1
if(dp[i]>max){
max = dp[i];
}
}
else{
dp[i-1] = 1;//前面元素重置
dp[i] = dp[i-1]+1;//后面元素加1
if(dp[i]>max){
max = dp[i];
}
}
}
printf("%d\n",max);
}
return 0;
}