Maximum Index

Given an array Arr[] of N positive integers. The task is to find the maximum of j - i subjected to the constraint of Arr[i] <= Arr[j].

• Time : O(n)
• Space : O(n)

class Solution{
public:
    int maxIndexDiff(int arr[], int n) {
        vector<int> midp(n), madp(n);
        for(int i = 0, mi = INT_MAX; i < n; i++) {
            mi = min(mi, arr[i]);
            midp[i] = mi;
        }
        for(int i = n - 1, ma = INT_MIN; i >= 0; i--) {
            ma = max(ma, arr[i]);
            madp[i] = ma;
        }
        int i = 0, j = 0, res = 0;
        while(i < n and j < n) {
            if(midp[i] <= madp[j]) {
                res = max(res, j - i);
                j++;
            } else i++;
        }
        return res;
    }

};