Medium
Quiz
#1465 Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
APPROACH
A rectangular cake measures h x w. You are given arrays horizontalCuts and verticalCuts specifying cut distances from the top and left edges respectively. After making all specified cuts, find the area of the largest resulting piece. Return this area modulo 109 + 7.
Example 1:
Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.
Example 2:
Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.
Example 3:
Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9
1 of 4
1:00
What is the optimal approach for this problem?