Maximum Index

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

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

class Solution{
public:
    int maxIndexDiff(int A[], int N) {
        int res = 0;
        vector<int> mi(N), ma(N);
        mi[0] = A[0], ma[N-1] = A[N-1];
        for(int i = 1; i < N; i++)
            mi[i] = min(mi[i-1], A[i]);
        for(int i = N - 2; i >= 0; i--)
            ma[i] = max(ma[i+1], A[i]);
        int i = 0, j = 0;
        while(i < N and j < N) {
            if(mi[i] <= ma[j]) {
                res = max(res, j - i);
                j++;
            } else i++;
        }
        return res;
    }
};