11. Container With Most Water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

思考：想用分治思想来解决这个问题，（a1,...,an-1) 和（a1,...,an-1,an）答案之间的关系是

S（a1,...,an-1) = max {S(a1,...,an-1), max(an作为右边，右边分别为a1到an-1）}

实现算法如下。

 1 int maxArea(int* height, int heightSize) {
 2     if(heightSize == 2) 
 3         return ((height[heightSize-1]>=height[heightSize-2])?height[heightSize-2]:height[heightSize-1]);
 4     
 5     int tmp,compare1,compare2,result,i;
 6     
 7     compare1 = (heightSize - (heightSize-1))*((height[heightSize-1]>=height[heightSize-2])?height[heightSize-2]:height[heightSize-1]);
 8     for(i=heightSize-2; i>0; i--) {
 9         tmp = (heightSize - i)*((height[heightSize-1]>=height[i-1])?height[i-1]:height[heightSize-1]);
10         if(tmp>compare1) compare1 = tmp;
11     }
12     
13     compare2 = maxArea(height, heightSize-1);
14     if(compare2>compare1) 
15         result = compare2;
16     else
17         result = compare1;
18     
19     return result;
20 }

可是运行结果是时间超时了，分析下运行时间，递归深度为n,至顶而下，每一层的操作数分别为，n，n-1,n-2,...,2.为O(n平方）。超出时间。网上看了下这个博客的思路，自己实现了，如下。

http://bangbingsyb.blogspot.tw/2014/11/leetcode-container-with-most-water.html

 1 int maxArea(int* height, int heightSize) {
 2 
 3     int index1 = 1;
 4     int index2 = heightSize;
 5     int max = ((height[index1-1]>=height[index2-1])?height[index2-1]:height[index1-1])*(index2-index1);
 6     int i,j,tmp;
 7     
 8     i = 1;
 9     j = heightSize;
10     while(j-i) {
11         if(height[j-1]>=height[i-1])
12             i++;
13         else
14             j--;
15         tmp = ((height[i-1]>=height[j-1])?height[j-1]:height[i-1])*(j-i);
16         if(tmp>max) max = tmp;
17     }
18     
19     return max;
20 }