Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Given an array arrA[], find the maximum j – i such that arr[j] > arr[i].

Objec­tive: Given an array arrA[], find the max­i­mum j – i such that arr[j] > arr[i].
Exam­ple:

int[] arrA = { 12, 3, 1, 5, 6, 4, 10, 9, 8, 0 };
Output: Max(j-i) where j>i and A[j]>A[i] is : 7

Approach:

  • Cre­ate 2 Aux­i­lary Arrays say Lmin[] and Rmax[] of the same size as main array
  • Put Lmin[0]=0 and Rmax[Rmax.length-1] =Rmax.length-1
  • Tra­verse the main array and fill the Lmin array with the index posi­tion which has the min­i­mum value so far
  • Tra­verse the main array back­words and fill the Rmax array with the index posi­tion which has the max­imun value so far
  • Ini­tial­ize distance_so_far = 0
  • Nav­i­gate through the main array and if (Lmin[i]<Rmax[i])
  • Then check if (Rmax[i]-Lmin[i])>distance_so_far then distance_so_far = Rmax[i]-Lmin[i]
  • Return distance_so_far

Com­plete Code:


Out­put:

Max(j-i) where j>i and A[j]>A[i] is : 7

You may also like...