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.

Solution: Find left bound and right bound for each element. O(n).

 1 class Solution {
 2 public:
 3     int trap(int A[], int n) {
 4         int max_val = 0;
 5         int max_ind = 0;
 6         for(int i = 0; i < n; i++) {
 7             if(A[i] > max_val) {
 8                 max_val = A[i];
 9                 max_ind = i;
10             }
11         }
12         
13         int trap = 0;
14         int start = 0;
15         for(int i = start+1; i < max_ind; i++) {
16             if(A[i] < A[start]) {
17                 trap += A[start]-A[i];
18             }
19             else {
20                 start = i;
21             }
22         }
23         
24         start = n-1; //update start
25         for(int i = start-1; i > max_ind; i--) {
26             if(A[i] < A[start]) {
27                 trap += A[start]-A[i];
28             }
29             else{
30                 start = i;
31             }
32         }
33         return trap;
34     }
35 };