Given an array arr[], find the maximum j – i such that arr[j] > arr[i].
Examples:
Input: {34, 8, 10, 3, 2, 80, 30, 33, 1}Output: 6 (j = 7, i = 1)Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0}Output: 8 ( j = 8, i = 0)Input: {1, 2, 3, 4, 5, 6}Output: 5 (j = 5, i = 0)Input: {6, 5, 4, 3, 2, 1}Output: -1 To solve this problem, we need to get two optimum indexes of arr[]: left index i and right index j. For an element arr[i], we do not need to consider arr[i] for left index if there is an element smaller than arr[i] on left side of arr[i]. Similarly, if there is a greater element on right side of arr[j] then we do not need to consider this j for right index. So we construct two auxiliary arrays LMin[] and RMax[] such that LMin[i] holds the smallest element on left side of arr[i] including arr[i], and RMax[j] holds the greatest element on right side of arr[j] including arr[j]. After constructing these two auxiliary arrays, we traverse both of these arrays from left to right. While traversing LMin[] and RMa[] if we see that LMin[i] is greater than RMax[j], then we must move ahead in LMin[] (or do i++) because all elements on left of LMin[i] are greater than or equal to LMin[i]. Otherwise we must move ahead in RMax[j] to look for a greater j – i value.
Thanks to celicom for suggesting the algorithm for this method.
import java.util.*;
import java.lang.*;
import java.io.*;class GFG {public static int calcualteMax1(int[] array) {int max = 0;for(int i=0; i<array.length; i++){for(int j=i+1; j<array.length; j++){if(array[i]<array[j]){max = Math.max(max, j-i);}}}return max;}public static int calcualteMax2(int[] array) {int[] leftmin = new int[array.length];int[] rightmax = new int[array.length];leftmin[0] = array[0];for(int i=1; i<array.length; i++){if(array[i]<leftmin[i-1]){leftmin[i] = array[i];} else {leftmin[i] = leftmin[i-1];}}rightmax[array.length-1] = array[array.length-1];for(int j=array.length-2; j>=0; j--){if(array[j]>rightmax[j+1]){rightmax[j] = array[j];} else{rightmax[j] = rightmax[j+1];}}int i=0; int j=0; int max = 0;while(i<array.length && j<array.length){if(leftmin[i]<rightmax[j]){max = Math.max(max, j-i);j++;}else{i++;}}return max;}public static void main (String[] args) {//codeScanner scanner = new Scanner(System.in);int n = scanner.nextInt();for(int i=0; i<n; i++){int length = scanner.nextInt();int[] array = new int[length];for(int j=0; j<length; j++){array[j] = scanner.nextInt();}System.out.println(calcualteMax2(array));}}}
