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!

Solution: 

The problem is actually to find the maximum, the second maximum, the third maximum.etc.
So the water that hold at one point has to do with the left maximum and right maximum, compare them to get min(leftmax,rightmax ) we have the water at  each point,
Bear in mind, need to compare it with the bar value at that point also

Code:

int trap(int A[], int n)
{
    if (n<3 0="" return="" span="">

        int *l = new int[n];
        int *r = new int[n];

        int water =0;

        l[0]=0;
        for (int i=1;i
            l[i]= max(l[i-1], A[i-1]);
        }

        r[n-1] = 0;
        for (int i=n-2;i>=0;i--){
            r[i]=max(r[i+1],A[i+1]);
        }

        for (int i=0;i
            if (min(l[i],r[i])-A[i] >0 ){
                water += min(l[i],r[i])-A[i];
            }
        }

        return water;
}