findMaxDiffIdx.cc

/*
num[i] > num[j], i < j, find max j-i

example:
[3 4 5 1 3]
   i     j
*/

#include <vector>
#include <string>
#include <iostream>

using namespace std;

int findMaxDiffIdx(vector<int> arr) {
    int n = arr.size();
    
    // largest value on the left of j
    vector<int> LMax = vector<int>(n, 0);
    
    // smallest value on the right side of i
    vector<int> RMin = vector<int>(n, 0);
    
    LMax[0] = arr[0];
    for (int i = 1; i < n; i++) {
        LMax[i] = max(LMax[i-1], arr[i]);
    }
    
    RMin[n-1] = arr[n-1];
    for (int i = n - 2; i >= 0; i--) {
        RMin[i] = min(RMin[i+1], arr[i]);
    }
    
    int i = 0;
    int j = 0;
    int maxVal = 0;
    while (i < n && j < n) {
        if (LMax[i] > RMin[j]) {
            maxVal = max(maxVal, j - i);
            j++;
        } else {
            i++;
        }
    } 
    
    return maxVal;
}

int main() {
    vector<int> arr = {3,4,5,1,3};
    vector<int> arr2 = {12,32,32,0,43,5,34,35,34,36,31,32};
    int result = findMaxDiffIdx(arr2);
    cout << result << endl;
    
    return 0;
}