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.

Solution:

It can be solved using DP. It is that kind of DP that can choose intermediate sequences, i.e., suppose two endpoints are [a b], then a and b both can be from 0 to N-1.

For this problem, observation is that once one endpoint is fixed, such as b is fixed, to have the same capacity for all the choices of a, all the a pointers form a line with 45 degree angle to x-axis, while when a is fixed, all the b points that have the same capacity form a -45 degree angle line to x-axis. So it's like two lines of a pyramid.

This means to get the higher capacity, as we narrow down from both ends to the middle, we only need to consider those bigger than previous, viz., height[a(i+1)] > height[a(i-1)] , height[b(i+1)] > height[b(i)] 

Code:

    int maxArea(vector &height) {

            int len = height.size(), low = 0, high = len -1 ;

       int maxArea = 0;

       while (low < high) {

         maxArea = max(maxArea, (high - low) * min(height[low], height[high]));

         if (height[low] < height[high]) {

           low++;

         } else {

           high--;

         }

       }

       return maxArea;

    }