Problem Killer
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2808 Accepted Submission(s): 605
Problem Description
You are a "Problem Killer", you want to solve many problems.
Now you have n problems, the i-th problem's difficulty is represented by an integer ai (1≤ai≤109).
For some strange reason, you must choose some integer l and r (1≤l≤r≤n), and solve the problems between the l-th and the r-th, and these problems' difficulties must form an AP (Arithmetic Progression) or a GP (Geometric Progression).
So how many problems can you solve at most?
You can find the definitions of AP and GP by the following links:
https://en.wikipedia.org/wiki/Arithmetic_progression
https://en.wikipedia.org/wiki/Geometric_progression
Now you have n problems, the i-th problem's difficulty is represented by an integer ai (1≤ai≤109).
For some strange reason, you must choose some integer l and r (1≤l≤r≤n), and solve the problems between the l-th and the r-th, and these problems' difficulties must form an AP (Arithmetic Progression) or a GP (Geometric Progression).
So how many problems can you solve at most?
You can find the definitions of AP and GP by the following links:
https://en.wikipedia.org/wiki/Arithmetic_progression
https://en.wikipedia.org/wiki/Geometric_progression
Input
The first line contains a single integer T, indicating the number of cases.
For each test case, the first line contains a single integer n, the second line contains n integers a1,a2,⋯,an.
T≤104,∑n≤106
For each test case, the first line contains a single integer n, the second line contains n integers a1,a2,⋯,an.
T≤104,∑n≤106
Output
For each test case, output one line with a single integer, representing the answer.
Sample Input
2
5
1 2 3 4 6
10
1 1 1 1 1 1 2 3 4 5
Sample Output
4
6
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int N = 1000000 + 5; 6 7 int T, n; 8 9 int a[N], b[N]; 10 11 double q[N]; 12 13 int main(){ 14 scanf("%d", &T); 15 while(T--){ 16 scanf("%d", &n); 17 a[0] = 0; 18 scanf("%d", &a[1]); 19 for(int i = 2; i <= n; i ++){ 20 scanf("%d", a + i); 21 b[i] = a[i] - a[i-1]; 22 } 23 int cnt = 2; 24 int ans = 0; 25 /*for(int i = 1; i <= n; i ++) 26 printf("%d ", b[i]); 27 /*for(int i = 1; i <= n; i ++) 28 printf("%.2f ", q[i]);*/ 29 for(int i = 3; i <= n; i ++){ 30 if(b[i] == b[i-1]){ 31 cnt += 1; 32 continue; 33 } 34 else{ 35 ans = max(cnt, ans); 36 cnt = 1; 37 if(a[i-1] + a[i+1] == 2 * a[i]) cnt += 1; 38 } 39 } 40 ans = max(ans, cnt); 41 //printf("ans = %d ", ans); 42 cnt = 1; 43 for(int i = 2; i < n; i ++){ 44 if(1ll * a[i] * a[i] == 1ll * a[i-1] * a[i+1]){ 45 cnt ++; 46 } 47 else{ 48 ans = max(ans, cnt + 1); 49 cnt = 1; 50 if(1ll * a[i] * a[i] == 1ll * a[i-1] * a[i + 1]) cnt += 1; 51 } 52 } 53 if(1ll * a[n-1] * a[n-1] == 1ll * a[n-2] *a[n]) cnt += 1; 54 ans = max(ans, cnt); 55 if(n == 0) ans = 0; 56 if(n == 1) ans = 1; 57 if(n == 2) ans = 2; 58 printf("%d ", ans); 59 } 60 return 0; 61 }