Google kickstart round E 2020

problem A:

video explanation:

Problem

An arithmetic array is an array that contains at least two integers and the differences between consecutive integers are equal. For example, [9, 10], [3, 3, 3], and [9, 7, 5, 3] are arithmetic arrays, while [1, 3, 3, 7], [2, 1, 2], and [1, 2, 4] are not arithmetic arrays.

Sarasvati has an array of N non-negative integers. The i-th integer of the array is Ai. She wants to choose a contiguous arithmetic subarray from her array that has the maximum length. Please help her to determine the length of the longest contiguous arithmetic subarray.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Ai.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the length of the longest contiguous arithmetic subarray.

Solution:

Consider a subarray of length K which is an arithmetic subarray, and let the elements of arithmetic subarray be B1, B2, B3, ….., BK. We can say that B2 — B1 = Bi+1 — Bi for 1 ≤ i < K, because consecutive elements of arithmetic sequence should have a common difference.

In the given array, consider a subarray starting at index i and ending at index j. Now if this subarray is not arithmetic, there exists some index x such that i ≤ x < j and Ax+1 — Ax ≠ Ai+1-Ai. All subarrays starting at index i and ending at index y such that x < y ≤ N, are not arithmetic because all such subarrays would contain index x such that Ax+1 — Ax ≠ Ai+1-Ai.

We can conclude our approach as follows. Initialise the answer as 0. We maintain two pointers, left pointer i and right pointer j. For an index i, we try to find the longest arithmetic subarray starting at index i by incrementing j. Let the maximum j for index i such that subarray(i,j) is an arithmetic subarray be max_j. Update answer if max_j — i + 1 is greater than current answer. And then we shift our left pointer i to the current max_j. We can see that both the pointers visit each element at most once. Hence, the complexity of the solution is O(N).

Code:

#include <bits/stdc++.h>

using namespace std;

int main() {
int t;
cin>>t;
int n;
for(int i=0;i<t;i++){
cin>>n;
int arr[n];
for(int j=0;j<n;j++){
cin>>arr[j];
}
int diff=0;
int ans=1;
int length=-1;

for(int j=0;j<n;j++){
if(j==0){
diff=arr[j+1]-arr[j];
}
else{
if(arr[j]-arr[j-1]==diff){
ans++;

}
else{
diff=arr[j]-arr[j-1];
if(ans>length){
length=ans;
}

ans=2;
}
}
}
if(length<ans){
length=ans;}


cout<<”Case #”<<i+1<<”: “<<length<<endl;



}
}