矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
-
horizontalCuts[i]是从矩形蛋糕顶部到第i个水平切口的距离 verticalCuts[j]是从矩形蛋糕的左侧到第j个竖直切口的距离
请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 109 + 7 取余 后返回。
示例 1：
输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3] 输出：4 解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色的那份蛋糕面积最大。
示例 2：
输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1] 输出：6 解释：上图所示的矩阵蛋糕中，红色线表示水平和竖直方向上的切口。切割蛋糕后，绿色和黄色的两份蛋糕面积最大。
示例 3：
输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3] 输出：9
提示：
2 <= h, w <= 1091 <= horizontalCuts.length <= min(h - 1, 105)1 <= verticalCuts.length <= min(w - 1, 105)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < w- 题目数据保证
horizontalCuts中的所有元素各不相同 - 题目数据保证
verticalCuts中的所有元素各不相同
1.分治法：每次切割都将原来的图分割成两部分，然后对于被分割出来的两部分再进行分割，直到不能分割为止。剪枝：先对分割序列进行排序，这样就可以实现：先从上往下横着切，再从左到右竖着切。这样一来，对于横切部分，划分成上下两半，（若升序排序）上半边已经不会再被切割了，所以对上半边进行递归的时候可以把水平切割队列置空；对于竖切部分同理。
1 class Solution 2 { 3 public: 4 vector<int> none; 5 long long max_area = 0; 6 long long mod = 1e9 + 7; 7 void divideArea(long long bx, long long by, long long ex, long long ey, vector<int> horizontalCuts, vector<int> verticalCuts) 8 { // bx、by为区域左上角坐标，ex、ey为区域右下角坐标 9 10 if (!horizontalCuts.empty()) 11 { 12 int row = horizontalCuts.front(); 13 horizontalCuts.erase(horizontalCuts.begin()); 14 divideArea(bx, by, row, ey, none, verticalCuts); // 上部 15 divideArea(row, by, ex, ey, horizontalCuts, verticalCuts); // 下部 16 } 17 else if (!verticalCuts.empty()) 18 { 19 int column = verticalCuts.front(); 20 verticalCuts.erase(verticalCuts.begin()); 21 divideArea(bx, by, ex, column, none, none); // 左部 22 divideArea(bx, column, ex, ey, none, verticalCuts); // 右部 23 } 24 else 25 { // 切割完毕，更新最大面积 26 max_area = max(max_area, (ey - by) * (ex - bx)); 27 } 28 } 29 int maxArea(int h, int w, vector<int> &horizontalCuts, vector<int> &verticalCuts) 30 { 31 sort(horizontalCuts.begin(), horizontalCuts.end()); 32 sort(verticalCuts.begin(), verticalCuts.end()); 33 divideArea(0, 0, h, w, horizontalCuts, verticalCuts); 34 return max_area % mod; 35 } 36 };
该代码不能通过最后一组用例，因为空间复杂度爆了，暂时没找到优化的点，仅供思路参考。
2.贪心法：我们注意到他的每次切割都是水平或垂直的完全切割，也就是说每次不同方向切割都能相互影响（例如横切过2刀之后，蛋糕被分成了三块，此时竖切一刀，这时的三块蛋糕都会同时受到影响），所以我们只需考虑横切完后的最大间距和竖切完后的最大间距，他们围成的面积就是最大的。
1 class Solution 2 { 3 public: 4 long long mod = 1e9 + 7; 5 6 long long maxInterval(vector<int> arr, int border) 7 { 8 int mmax = border - *arr.rbegin(); //初值为最后一块的长度 9 int pre = 0; 10 for (int i : arr) 11 { 12 mmax = max(i - pre, mmax); 13 pre = i; 14 } 15 return mmax; 16 } 17 int maxArea(int h, int w, vector<int> &horizontalCuts, vector<int> &verticalCuts) 18 { 19 sort(horizontalCuts.begin(), horizontalCuts.end()); 20 sort(verticalCuts.begin(), verticalCuts.end()); 21 return maxInterval(horizontalCuts, h) * maxInterval(verticalCuts, w) % mod; 22 } 23 };