11. Container with most water
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) 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.
Example:
Input: [1,8,6,2,5,4,8,3,7]
Output: 49
网上给出的最优算法都比较类似，其基本想法是：将挑选的两条边分别从两端开始向中间移动，每一次只能移动两条边中的一条。每次移动的标准是将较小的那条边往中间移动一格。如果移动后的面积有所增长，则将面积最大值更新。当两条边相遇时，则停止。
网上几乎都只有这个算法的描述，而没有提供一个严格的数学证明。和好友Meiyf讨论后，整理出这个算法的数学证明。
考虑分布在左右两边的移动指标，它们分别从两端
开始，通过
右移、
左移的方式，来搜索最优解。
假设最优解为，则我们有：
。根据算法的移动方式，总是可以通过“
从
右移、
从
左移”若干步的方式，到达
。
由于算法每一次只能移动一步（即右移一步或
左移一步），所以两种情况：
-
先到达
-
先到达
必然有一种先发生。不妨假设先到达
（那么此时，
也就还未通过左移到达
，它还在
的右侧）。那么，我们只需证明：
在现有的算法下，后续的更新步骤都只能是：
。
我们可以通过反证法来证明上述结论。
令函数表示点
对应的线段长度，令
表示点
和
构成的线段长度。
若假设不成立，则存在某一步：在
的
下面我们来证明不可能出现上面这种情况。
若上述发生，则我们有以下结论：
-
。因为根据算法，只有长度更小的那一条边才能向中间移动。所以，只有当
小于
时，才可能出现
由此，我们可以得到由两条边形成的面积为：
这里的高度之所以取为，是因为上面第2条已经说明了
比
小。
而此时，因为第1条已经说明，所以
。所以我们有：
矛盾。所以假设命题不成立，进而当到达
后，后续的所有更新步骤都只能是
不断左移、直到到达
。
所以，在这样的算法之下，一定能够到找到面积的最优解。
网友评论