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
網上給出的最優算法都比較類似，其基本想法是：将挑選的兩條邊分别從兩端$a_0, a_n$開始向中間移動，每一次隻能移動兩條邊中的一條。每次移動的标準是将較小的那條邊往中間移動一格。如果移動後的面積有所增長，則将面積最大值更新。當兩條邊相遇時，則停止。
網上幾乎都隻有這個算法的描述，而沒有提供一個嚴格的數學證明。和好友Meiyf讨論後，整理出這個算法的數學證明。
考慮分布在左右兩邊的移動名額$a_l, a_r$，它們分别從兩端$a_0, a_n$開始，通過$a_l$右移、$a_r$左移的方式，來搜尋最優解。
假設最優解為$a_i, a_j$，則我們有：$0 \leq i < j \leq n$。根據算法的移動方式，總是可以通過“$a_l$從$a_0$右移、$a_r$從$a_n$左移”若幹步的方式，到達$a_i, a_j$。
由于算法每一次隻能移動一步（即$a_l$右移一步或$a_r$左移一步），是以兩種情況：
- $a_l$先到達$a_i$
- $a_r$先到達$a_j$
必然有一種先發生。不妨假設$a_l$先到達$a_i$（那麼此時，$a_r$也就還未通過左移到達$a_j$，它還在$a_j$的右側）。那麼，我們隻需證明：
在現有的算法下，後續的更新步驟__都隻能是__：$a_r$不斷左移、直到到達$a_j$。
我們可以通過反證法來證明上述結論。
令函數$h(a_t)$表示點$a_t$對應的線段長度，令$w(a_s, a_t)$表示點$a_s$和$a_t$構成的線段長度。
若假設不成立，則存在某一步：在$a_r$還未通過左移到達$a_j$時，停留在$a_i$的$a_l$需要右移一步。
下面我們來證明不可能出現上面這種情況。
若上述發生，則我們有以下結論：
- $l = i < j < r$
- $h(a_i) = h(a_l) < h(a_r)$。因為根據算法，隻有長度更小的那一條邊才能向中間移動。是以，隻有當$h(a_l)$小于$h(a_r)$時，才可能出現$a_l$右移。
由此，我們可以得到由$a_i, a_r$兩條邊形成的面積為：
$$
S^* = h(a_i) * w(a_i, a_r).
這裡的高度之是以取為$h(a_i)$，是因為上面第2條已經說明了$h(a_i)$比$h(a_r)$小。
而此時，因為第1條已經說明$j < r$，是以$w(a_i, a_r) > w(a_i, a_j)$。是以我們有：
S^* = h(a_i) * w(a_i, a_r) > h(a_i) * w(a_i, a_j) \geq \min{\{h(a_i), h(a_j)\}} * w(a_i, a_j) = S_{max}
沖突。是以假設命題不成立，進而當$a_l$到達$a_i$後，後續的所有更新步驟都隻能是$a_r$不斷左移、直到到達$a_j$。
是以，在這樣的算法之下，一定能夠到找到面積的最優解$S_{max}$。
如果你喜歡我的文章或分享，請長按下面的二維碼關注我的微信公衆号，謝謝！
更多資訊交流和觀點分享，可加入知識星球：
