Arrays & Strings

Problem 
Print all the maxima elements in the array i.e elements which are greater than all the elements on the right side of that element in that array.
Consider the array : { 37 , 19 , 4 , 27 , 23 }
Maxima elements are 23, 27 & 37 [ Rightmost element is always a maxima element ]

Solution 
1) Start traversing array from the end and keep track of the max element.
2) If we encounter an element > max, print the element and update max.

#include<iostream>
using namespace std;

// print all maxima elements in the array
// an element is a maxima when it is greater than all the
// elements to it's right
void printMaxima(int arr[],int size) {
   int max = arr[size-1];
   int j;
   cout<<max<<" "; // rightmost element is always a maxima
   for (j=size-2;j>=0;j--) {
      if (arr[j] > max) {
         cout<<arr[j]<<" ";
         max = arr[j];
      }
   }
}

// main
int main() {
   int arr[] = {37,19,4,27,23};
   int size = sizeof(arr)/sizeof(arr[0]);
   printMaxima(arr,size);
   cout<<endl;
   return 0;
}

Back | Next