Understanding the problem
Suppose we start from the left and continue, we would stop at a height >= where we started,
and then calculate the water = left * (k - j - 1) - sum(blocks in the way).
Now, apply the same logic to the largest and 2nd largest heights. Basically, we cut the maximum height to be
the 2nd maximum height for each case (of selection of region).
We will basically after finding water between them,
the part on the left and right are completely independent.
So we do have optimal substructure.
But we don't have overlapping subproblems. So this can be done by divide and conquer.
trap(i, j) = trap(i, a) + water(a...b) + trap(b, j) where a, b are first and second maximas (in any order).
Trap will return a number.
Also, we can reuse the walls of a region for outer regions.
*/
/*
Approach 1 - simple recursion is optimal? because we have no overlapping subproblems, so nothing to store.
And recursion is a must because input selection is variable for each case.
As we are doing everything optimally, this is optimal? Is it?
By the way, this gave TLE error on LeetCode.
Consider this problem to understand Trapping Water - LeetCode
By the way, this gave TLE error on LeetCode.