I like the recursive solution to this.

Here is my recursive solution.
class Solution { public: int trap(int A[], int n) { int left = 0, right = n  1; int height = A[left] < A[right] ? A[left] : A[right]; int max = 1, index = 1; for(int i = left + 1; i < right; i++) { if(A[i] > max) { max = A[i]; index = i; } } if(height < max) return trap(A, index + 1) + trap(A + index, right  index + 1); int sum = (right  left  1) * height; if(sum <= 0) return 0; for(int i = left + 1; i < right; i++) { sum = height < A[i] ? height : A[i]; } return sum; } };