Maximum width ramp (leetcode 962)

maximum_width_ramp.cpp

class Solution {
public:
    int maxWidthRamp(vector<int>& A) {
        map<int, int> largest;
        largest[A.back()] = A.size()-1;
        int max_width = 0;
        for (int i = A.size()-2; i >= 0; --i) {
            auto found = largest.lower_bound(A[i]);
            if (found != largest.cend()) {
                max_width = max(max_width, found->second - i);
            }
            if (A[i] > largest.rbegin()->first) {
                largest[A[i]] = i;
            }
        }
        return max_width;
    }
};