The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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

All problems on Arrays and Strings
* Reverse an array in place
* Sort an array of 0s and 1s
* Sort an array of 0s, 1s and 2s
* Print all the maxima elements in the array
* Check if two strings are anagrams
* Find the duplicate array elements
* Find the minimum element in a sorted and rotated array
* Remove all duplicate characters in a string
* Find two array elements which sum upto a target value
* Find the median of two sorted arrays
* Find if a sub-array of consecutive elements of size p exists which sum upto a target value
* Find the maximum difference between two elements in an array s.t larger element appears after the smaller element in the array
* Find the largest sum contiguous subarray
* Find the smallest positive element missing in the given array of size n consisting of both positive & negative integers
* Given an array of n elements, find max( j - i ) s.t arr(j) > arr(i)