PROBLEM LINK:
Author & Editorialist: Pulkit Sharma
Tester: Satyam Gupta
DIFFICULTY:
CAKEWALK
PREREQUISITES:
loops (Array Traversal)
PROBLEM:
Given an array A of size N , find out the size of the largest subarray containing identical elements.
EXPLANATION:
Before explaining the solution, I would like to give you a quick tip.
Whenever you read a problem statement , make sure you know that what is the worst case time complexity required such the time
limit can be passed.
For this problem number of test cases = 100
And each test case contains an array of 100000 numbers at max. (The array elements themselves need not be considered while calculating time complexity in this case)
So, there will be atleast 100000*100 = 10^7 things to do for this problem.
A 1 second time limit permits about 10^7 things to do.
From the above observation it is pretty clear that O(n) solution will pass the time complexity and an O(n^2) would not( as it would take 100*100000*100000 = 10^{12} iterations.)
We can iterate over the array and keep track of the maximum length of subarray of identical elements.
The following procedure will help you understand.
Let max_len = 0 and len_trav = 0, initially.
If we find that the previous and present values are same, then we will increment the length of the array traversed(len_trav).
When we find a mismatch, we will make update the max_len, only if he current length traversed is greater than max_len.
After this, we need to make length traversed to zero as a new section of identical elements may begin.
Repeat the above procedure for elements of the array.
The answer will be maxlen-1 , as the first element of the subarray will be the day when he told a Lie.
AUTHOR’S SOLUTION:
#include <bits/stdc++.h>
using namespace std;
int main()
{
//freopen("PINOCH2.in","r",stdin);
//freopen("PINOCH2.out","w",stdout);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int prev_val,new_val,dist = 0,ans = 0;
cin>>prev_val;
for(int i = 1 ; i < n ; i++)
{
cin>>new_val;
dist++;
if(new_val != prev_val)
{
dist = 0;
}
ans = max(ans,dist);
prev_val = new_val;
}
cout<<ans<<endl;
}
return 0;
}