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

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

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

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

Read full article from Given an array arrA[], find the maximum j – i such that arr[j] > arr[i]. | Algorithms