Trapping Rain Water

 1 public class Solution {
 2     public int trap(int[] A) {
 3         int waterSum = 0;
 4         int leftMaxHeight[] = new int[A.length];
 5         int rightMaxHeight[] = new int[A.length];
 6         
 7         int maxHeight = 0;
 8         for(int i = 0; i < A.length; i++){
 9             leftMaxHeight[i] = maxHeight;
10             maxHeight = maxHeight > A[i] ? maxHeight : A[i];
11         }//for
12         
13         maxHeight = 0;
14         for(int i = A.length - 1; i >= 0; i--){
15             rightMaxHeight[i] = maxHeight;
16             maxHeight = maxHeight > A[i] ? maxHeight : A[i];
17         }//for
18         
19         for(int i = 0; i < A.length; i++){
20             int minHeight = Math.min(leftMaxHeight[i], rightMaxHeight[i]);
21             int elementSum = minHeight - A[i];
22             if(elementSum > 0)
23                 waterSum += elementSum;
24         }//for
25         
26         return waterSum;
27     }
28     
29 }