0 like 0 dislike
1,346 views
Time Complexity should be O(N)  .

Example array :

{2,2,3,3,3,3,3,5,5,5,5,5,6}

Answer : 10  {3,3,3,3,3,5,5,5,5,5} is the longest subarray which is valid :)
| 1,346 views

0 like 0 dislike

C++ code:-

```#include <bits/stdc++.h>
using namespace std;
typedef long long int ll ;
int main()
{
vector <ll> b  ;
ll n ;
cin>>n ;
ll a[n+2]={0};
ll i  = 1 ;
while(i<=n)
{

cin>>a[i];

i++;
}

ll c = 0  ;
i=2;
while(i<=n)
{
if(a[i]==a[i-1])
{
c++;
}
else
{

b.push_back(c+1) ;

c=0;
}

i++;
}

b.push_back(c+1) ;

ll g = b.size() ;

ll maxim = 0 ;
i=0;
while(i<g-1)
{
//cout<<b[i]<<" ";
ll answer = b[i] + b[i+1] ;

i++;
}

cout<<maxim ;

return 0;
}
```

We break array into parts of same elements.
Say we have :  1,1,1,1,2,2,2,3,3,3,3,3,3,3,3.
After breaking we get :-
{1,1,1,1} , {2,2,2} , {3,3,3,3,3,3,3,3}
write them into frequencies we get :
{4},{2},{8}
new array is : [4,2,8]
In this array you just have to find 2 adjacent elements with maximum sum which can be done in O(n) in a single traversal . My code takes O(n) time and O(n) auxiliary space ,  O(1) auxliary space is possible too , but it will be messy to implement.

by Expert (110,440 points)