An easy-to-understand recursive explanation of the editorial solution


  • 0
    N

    Let C(1, n) denote the problem of finding the largest container given a1, a2, ..., an. Without loss of generality, let's assume a1 < an. Then there are only two possibilities: The largest container has (1, a1) as the left side, or it does not. For the first possibility, the right side of the largest container must be (n, an), which has been explained. For the second possibility, it is the problem C(2, n). To solve C(2, n), we increment the left pointer by 1.Then, to solve C(1, n), we only need to compare the results of both possibilities. In the case that a1 >= an, the argument remains similar. This is exactly what the solution does.

    We are still using recursion in this problem, but the nuance is that we cannot break the problem into a subproblem in a particular direction as in most cases, say, breaking C(1, n) into C(1, n-1). We have to make a decision to break C(1, n) into C(1, n-1) or C(2, n), depending on the input.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.