Program to find leader in an array

Everything in the right should be smaller than current element.Two method are there.First method is brute force method but the complexity is O(n^3).But the method 2 is optimal solution that complexity is O(n).


For example

a[4]={1,5,4,3}

In the given array  1 is not leader because all the element right from 1 is greater.

5 is leader element because all the element from right from 5 is smaller than 5.

4 and 3 is also leader element.

So leader element is {5,4,3}


Method 1: brute force to find leader in a array.

#include<stdio.h>

void main() {

   int a[4]={1,5,4,3};

   int n=4;

   int i,j;

   int flag;

   int ans[3];

   for(i=0;i<n;i++)

   {

       flag=1;

       for(j=i+1;j<n;j++)

       {

           if(a[j]>a[i])

           {

               flag=0;

               break;

           }

       }

   if(flag==1)

   printf("%d",a[i]); 

   }

}

Output

5

4

3

Brute force solution is not good because complexity O(n^3)

Method 2:Optimal solution to find leader in array.

#include<stdio.h>

void main() {

   int a[4]={1,5,4,3};

   int n=4;

   int i;

   int max=0;

   for(i=n-1;i>0;i--)

   {

           if(a[i]>max)

           {

              printf("%d",a[i]);

              max=a[i];

           }

       }  

}

Output

5

4

3

But the method 2 is optimal solution that complexity is O(n).