This is a problem in leetcode: https://leetcode.com/problems/container-with-most-water/description/
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
This is the code that I wrote:
class Solution:
def maxArea(self, height: List[int]) -> int:
maxvol = 0
lo = 0
hi = len(height)-1
while lo < hi:
vol = (hi-lo)*min(height[lo],height[hi])
if maxvol < vol: maxvol = vol
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return maxvol
My question is correctness of the code. There are two indices running lo and hi, so I am trying to set up an induction hypothesis on these two indices:
IH: for any i <= lo and j >= hi, vol(i,j) <= maxvol, where vol(i,j) is volume formed by ith and jth index of height.
Base case is trivial, so I shall assume that IH is correct for some index lo and hi. Suppose height[lo] < height[hi], so lo = lo+1. There shall be maxvol corresponding to two indices lo and hi.
Now, I need to prove that: for all i <= lo and j >= hi, vol(i,j) <= maxvol. The problem arises when i = lo. I know that vol(lo',hi) <= maxvol and maxvol <= maxvol, but how can I successfully assert that vol(lo,j) <= maxvol for all j >= hi?