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!

int trap(int A[], int n){	int left[n];	int right[n];	int leftMax = 0;	for (int i = 0; i < n; i++)	{		left[i] = leftMax;		leftMax = max(leftMax, A[i]);	}	int rightMax = 0;	for (int i = n-1; i >= 0; i--)	{		right[i] = rightMax;		rightMax = max(rightMax, A[i]);	}	int result = 0;	for (int i = 0; i < n; i++)	{		int temp = min(left[i], right[i]) - A[i];		if (temp > 0)		{			result += temp;		}	}	return result;}