#### Arrays & Strings

Problem
Given an array of ‘n’ elements, find max( j – i ) s.t arr(j) > arr(i).
Consider the array { 7, 2, 6, 3, 5, 1 } .
Max( j – i ) = 3 where j = 4 & i = 1 and arr(4) > arr(1).

Solution
We need to maintain two temporary arrays min_from_left (Value at each index is the min value found till that index starting from left) & max_from_right (Value at each index is max value found till that index starting from right). Let max_diff holds max ( j – i ). Iterate over the two temporary arrays and update max_diff.
See the implementation below.

```#include<iostream>
using namespace std;

int max(int x, int y) {
return ((x > y) ? x : y);
}

int min(int x, int y) {
return ((x < y) ? x : y);
}

// find max (j-i) s.t arr[j] > arr[i]
int findMaxDiffIndex(int arr[],int size) {
int max_diff;
// array in which each index holds the minimum element found
// so far starting from left
// i.e arr[i] = min(arr[0...i]);
int min_from_left[size];
// array in which each index holds the maximum element found
// so far starting from right
// i.e arr[j] = max(arr[j...size-1]);
int max_from_right[size];
int i,j;
min_from_left[0] = arr[0];
for (i=1;i<size;i++) {
min_from_left[i] = min(min_from_left[i-1],arr[i]);
}
max_from_right[size-1] = arr[size-1];
for (j=size-2;j>=0;j--) {
max_from_right[j] = max(max_from_right[j+1],arr[j]);
}
i = 0;
j = 0;
max_diff = -1;
// iterate over the two temporary arrays
while (i < size && j < size) {
if (min_from_left[i] < max_from_right[j]) {
// update the max diff
max_diff = max(max_diff,j-i);
j++;
}
else {
i++;
}
}
return max_diff;
}

// main
int main() {
int arr[] = {29,11,7,19,62,24,1,5};
int size = sizeof(arr)/sizeof(arr[0]);
int max_diff = findMaxDiffIndex(arr,size);
cout<<"\nMax Index Difference :: "<<max_diff;
cout<<endl;
return 0;
}```