Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
You are given a rectangular cake of size h x w and two arrays of integers horizontalCuts and verticalCuts where:
horizontalCuts[i]is the distance from the top of the rectangular cake to thei^thhorizontal cut.verticalCuts[j]is the distance from the left of the rectangular cake to thej^thvertical cut.
Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a large number, return this modulo 10^9 + 7.
Example 1
Input
h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]Output
4After all cuts, the largest piece has area 4.
Example 2
Input
h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]Output
6After all cuts, the largest pieces have area 6.
Constraints
- 2 <= h, w <= 10^9
- 1 <= horizontalCuts.length <= min(h - 1, 10^5)
- 1 <= verticalCuts.length <= min(w - 1, 10^5)
- 1 <= horizontalCuts[i] < h
- 1 <= verticalCuts[i] < w
- All the elements in
horizontalCutsare distinct. - All the elements in
verticalCutsare distinct.