I was reading the solution and it said " For each of the O(200^3) rectangles that we consider in the one-rectangle scenario, we can also cache the four lines that touch the borders of those rectangles, and which side of the line that rectangle lies on. We can then consider every horizontal and vertical line and combine the two best rectangles on either side, and save the best result."
However, I don’t understand why does the optimal scenario necessarily have both rectangles from those 200^3?
If you split the barn by some vertical or horizontal line and find the best rectangle from each part independently, then both must be one of these 200^3.
Ex. Suppose that we split the original rectangle at x-coordinate t. Suppose that the best rectangle in [0,t]\times [0,200] is [x_1,x_2]\times [y_1,y_2] and the best rectangle in [t,200]\times [0,200] is [x_3,x_4]\times [y_3,y_4]. Both of these rectangles will be part of the 200^3 since they’ll be found when considering the pairs of x-coordinates (x_1,x_2) and (x_3,x_4), respectively.