0 like 0 dislike
479 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 :)
in Algorithms and Problems by Expert (19,320 points) | 479 views

1 Answer

0 like 0 dislike
Best answer

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] ; 
            maxim = max(maxim,answer) ; 
            
            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 (19,320 points)