ROTLEFT - Editorial

PROBLEM LINK:

Practice

Author: Tanishq Dhussa
Tester: Tanishq Dhussa
Editorialist: Tanishq Dhussa

DIFFICULTY:

SIMPLE

PREREQUISITES:

Greedy

PROBLEM:

A problem is to find Maximum no of elements who have all smaller elements to its right by rotating array.

QUICK EXPLANATION:

First we will traverse the array form right end and we will maintain max,if element is less than max we will increment the count after the whole array is traverse once we will see if maxcount is less than count then we will update maxcount.we will remove starting element from vector and add it to end and again we will repeate the procedure and perform rotation n-1 times. at last we will print maxcount

EXPLANATION:

This array contains :
count=0, maxcount=0
[1,2,19,20] Initially , Maximum no. of toppers is one i.e.[20].
count=1, maxcount=1
In 1st Rotation array -> [2,19,20,1].Maximum no. of toppers are two i.e.[20,1].
maxcount=2
In 2nd Rotation array -> [19,20,1,2].Maximum no. of toppers are two i.e.[20,2].
maxcount=2
In 3rd Rotation array -> [20,1,2,19].Maximum no. of toppers are two i.e.[20,19].
maxcount=2
So, the Maximum numbers of Topper are 2.

Answer: 2

SOLUTIONS:

#include<bits/stdc++.h>
using namespace std;

int main()
{
int T;
int n;
cin>>T;

while(T--)
{
    vector<int> v;
    long long int count=0;
    long long int maxCount=0;
    long long int max=0;
    cin>>n;
    for(int i=0; i<n;i++)
    {
        int ele;
        cin>>ele;
        v.push_back(ele);
    }
    for(int i=v.size()-1 ;i>=0;i--)
    {
        if(max<v[i])
        {
            max=v[i];
            count++;
        }
    }
    maxCount=count;
     count=0;
     for(int j=0 ;j<v.size()-1;j++)
     {
         int ele=v[0];
         v.erase(v.begin());
         v.push_back(ele);

         max=0;
         count=0;
         for(int i=v.size()-1 ;i>=0;i--)
        {
            if(max<v[i])
            {
                max=v[i];
                count++;
            }
        }
         if(count>maxCount)
             maxCount=count;
     }   
     cout<<maxCount<<endl;
}

}