Maximum Unsorted SubArray.cpp

// https://www.interviewbit.com/problems/maximum-unsorted-subarray/

vector<int> Solution::subUnsort(vector<int> &A) {
    int len = A.size();
    stack<pair<int,int> > s;

    int st = INT_MAX;
    int lst = -1;
    int mxIdx = 0;
    int mnIdx = INT_MAX;
    for(int i = 1; i < len; i++){
        int j = min(mxIdx, st);
        while(j >= 0 && A[j] > A[i]){
            st = min(st, j);
            j--;
        }
        if(A[mxIdx] <= A[i]){
            mxIdx = i;
        } else {
            lst = i;
        }

    }

    vector<int> ret;
    if(st != INT_MAX){
        ret.push_back(st);
        ret.push_back(lst);
    }
    else{
        ret.push_back(-1);
    }
    return ret;
}