Trapping Rain Water

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.Thanks Marcos for contributing this image!

class Solution {//pass small only
    int process(int A[], int start, int end){
        int r = 0;
        while(start < end){
            //squeeze out the heading and tailing zeros
            while(A[start] <= 0 && start < end){
                ++start;            
            }
            while(A[end] <= 0 && start < end){
                --end;            
            }
            if (start >= end) return r;
            for(int ii = start; ii <= end; ++ii){
                --A[ii];
                if (A[ii] < 0) ++r;
            }
        }
        return r;
    }
public:
    int trap(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        return process(A,0,n-1);
    }
}; 

//critical step is to find the max height and position
class Solution {//passed large test
public:
    int trap(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int max = 0;
        int max_index = 0;
        for(int ii = 0; ii < n; ++ii){
            if (A[ii] > max){
                max = A[ii];
                max_index = ii;
            }
        }//for ii ---> max
        vector<int> r(n,0);
        int lmax = 0;
        int lmax_index = 0;
        for(int ii = 0; ii < max_index; ++ii){
            if (A[ii] > lmax){
                lmax = A[ii];
                lmax_index = ii;
            }
            r[ii] += lmax - A[ii];
        }//for ii left max
        
        int rmax = 0;
        int rmax_index = 0;
        for(int ii = n-1; ii > max_index; --ii){
            if (A[ii] > rmax){
                rmax = A[ii];
                rmax_index = ii;
            }
            r[ii] += rmax - A[ii];
        }//for ii left max
        int sum = 0;
        for(int ii = 0; ii < n; ++ii) sum += r[ii];
        return sum;
    }
};