/**
 * This question could be solved with Dynamic Programming
 * Go through the array from both head and rear, calculate the area value.
 *     If head height is shorter than rear height, the head height could at
 *     most reach to the rear, hence we find the max area for head, any other
 *     combination with head would be less than these two, but we did not find
 *     limitation for rear, hence we just need to search max area in [head+1, rear]
 *     If rear height is shorter than head, is the same reason, just search max
 *     area in [head, rear-1]
 */
int maxArea(vector<int> &height) {
    int i = 0;
    int j = height.size();
    int maxVal = 0;

    while(i < j) {
        int minHeight = 0;

        if (height[i] < height[j]) {
            minHeight = height[i];
            ++i;
        } else {
            minHeight = height[j];
            --j;
        }

        // plus 1 because i or j has been modified above
        int area = (j-i+1)*minHeight;
        if (maxVal < area) {
            maxVal = area;
        }
    }
    

    return maxVal;
}