題目描述：
Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical 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 huge number, return this modulo 10^9 + 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
Constraints:
2 <= h, w <= 10^91 <= horizontalCuts.length < min(h, 10^5)1 <= verticalCuts.length < min(w, 10^5)1 <= horizontalCuts[i] < h1 <= verticalCuts[i] < wIt is guaranteed that all elements in
horizontalCutsare distinct.It is guaranteed that all elements in
verticalCutsare distinct.
題解：
這題給了我們四個信息，分別是一個矩型的高和寬，水平切線的數組和垂直切線的數組，並根據這幾個信息求出矩型中完成切割後最大的面積。
水平切線中的每一個元素的值代表在矩型的高上進行切割的位置。假如一個矩型的高是10，水平切線數組為 { 2, 5 }，那就代表將矩型從上到下分別切成3份，每份的高分別為2, 3, 5。
垂直切線中的每一個元素的值則代表在矩型的寬上進行切割。假如矩型寬為8，垂直切線數組為{ 3 }，那就代表將矩型從左到右切成2份，每份的寬分別為3, 5。
因此，解題思路就是找到每個切割元素之間的最大差值以及邊界（高/寬）與最後一個切割元素值的差之間最大的值。
首先，需要將切割元素排序，確保最後一位切割元素是最接近邊界的一條切割線。
然後，分別遍歷兩個切割數組。最大的寬度從垂直切割數組中得出；最大的高度從水平切割數組中得出。
最後再將元素中最大寬度和最大高度與它們對應的，最後一條切割線與邊界的差進行比較。
得出最終的最大高和寬後，將他們相乘得出面積。要注意的是，由於題目給的h和w可達到10^9的值，因此，兩者相乘有可能超出int的邊界，因此需要進行% 1000000007，確保值在int的範圍裡。
public class Solution {
public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
Array.Sort(horizontalCuts);
Array.Sort(verticalCuts);
long maxWidth = verticalCuts[0];
long maxHeight = horizontalCuts[0];
for (int i = 1; i < verticalCuts.Length; i++)
{
maxWidth = Math.Max(maxWidth, verticalCuts[i] - verticalCuts[i - 1]);
}
for (int i = 1; i < horizontalCuts.Length; i++)
{
maxHeight = Math.Max(maxHeight, horizontalCuts[i] - horizontalCuts[i - 1]);
}
if (w - verticalCuts[verticalCuts.Length - 1] > maxWidth)
{
maxWidth = w - verticalCuts[verticalCuts.Length - 1];
}
if (h - horizontalCuts[horizontalCuts.Length - 1] > maxHeight)
{
maxHeight = h - horizontalCuts[horizontalCuts.Length - 1];
}
return (int)(maxHeight * maxWidth % 1000000007);
}
}