Trapping Rain Drops

[Question]:

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.

[Analysis]:
The amount of rain that Ai can keep depends on the minimum of the maximum left/right (Aj, Ak), j<i<k. So need to find out maximum heights on Ai's left and right.

[Solution]:
//--- Java Code ---

public class Solution {

    public int trap(int[] A) {

        if (A.length <3) return 0;

        int[] leftHigh = new int[A.length];

        int[] rightHigh = new int[A.length];

        int lf = A[0];

        int rt = A[A.length-1];

        

        for (int i=1; i<A.length; i++) {

            leftHigh[i]=lf;

            if (A[i] > lf ) lf = A[i];

        }

        for (int i=A.length-2; i>=0; i--) {

            rightHigh[i] = rt;

            if (A[i] > rt ) rt = A[i];

        }

        int sum = 0;

        for (int i=1; i<A.length-1; i++) {

            int temp = Math.min(leftHigh[i], rightHigh[i]) - A[i];

            if (temp>0) sum+= temp;

        }

        return sum;

    }

}

//--- C++ Code ---
class Solution {
public:
    int trap(int A[], int n) {
        if (n<=2) return 0;
       
        int leftMax[n];
        int rightMax[n];
        int tmp = 0;
        for (int i=0; i<n; i++)
            tmp = leftMax[i] = max(tmp, A[i]);
    
        tmp=0;
        for (int i=n-1; i>=0; i--)
            tmp = rightMax[i] = max(tmp, A[i]);
       
        tmp=0;
        for (int i=0; i<n; i++)
            tmp+= min(leftMax[i], rightMax[i])-A[i];
           
        return tmp;
    }
};