How to think about it..! Develop intution
\n\nThanks to @interviewrecipes\n\nKey idea:\nIf we need the area, we must think of lengths and breadths of each cake piece.\n\nDevelop thinking..\n\nFirst, do 
![image](https://assets.leetcode.com/users/images/77740535-480a-4885-95ff-bc7c3c959af6_1656738187.1410081.png)\n\nThanks to @interviewrecipes\n\n**Key idea:**\nIf we need the area, we must think of lengths and breadths of each cake piece.\n\n**Develop thinking..**\n\nFirst, do not get overwhelmed by looking at the visual picture. You should know, the problem is made to solve.\nYou just have to change the thinking process.\n\nNow, approach:\nArea consitutes of **length * width**\n\nYou see the problem now becomes simple.\nFor maximizing the area, you need to **maximize the length and width**.\n\n`So, now you just have to find the maximum gap from given horizotal and vertical cuts.`\n\n**Assume**\nLENGTH as total horizontal length of the original cake.\nHEIGHT as total vertical height of the original cake.\nH as number of horizontal cuts. HCUTS is array of horizontal cuts.\nSimilarly, V as number of vertical cuts and VCUTS is an array of vertical cuts.\n\n**Solution**\n1. Lets only think of horizontal cuts. Each HCUTS[i] would create a piece with length LENGTH and height, say, heights[i]. As there are H cuts, there will be (H+1) pieces of length LENGTH.\n\n1. Now each vertical cut VCUTS[i] will cut each of the horizontal pieces that we got in step 1. We already know the height of each piece (step 1), now with each vertical cut, we will know the length of each piece as well.\n\n1. Because we want the maximize the area, we must try to maximize the length and height of each piece.\n\n\n**Algorithm**\n\n1. Find heights of pieces if we only perform the horizontal cuts. Say this array is heights[].\n1. Find lengths of pieces if we only perform the vertical cuts. Say this arrays is lengths[].\n1. Find max of heights[] and lengths[].\n1. Multiply those two max and take mod 10e7.\n1. Return the answer\n\n\n***Code 1 :*** Quick to understand, but a bit verbose.\n```\nclass Solution {\npublic:\n    const long long int mod = 1000000007;\n    int maxArea(int hh, int ww, vector<int>& h, vector<int>& v) {\n        // Sort\n        sort(h.begin(), h.end());\n        sort(v.begin(), v.end());\n        \n        \n        // Horizontal\n        vector<int> heights = {h[0]};\n        int nh = h.size();\n        for (int i=1; i<nh; i++) {\n            heights.push_back(h[i]-h[i-1]);\n        }\n        heights.push_back(hh-h[nh-1]);\n        \n        // Vertical\n        vector<int> lengths = {v[0]};\n        int nv = v.size();\n        for (int i=1; i<nv; i++) {\n            lengths.push_back(v[i]-v[i-1]);\n        }\n        lengths.push_back(ww-v[nv-1]);\n        \n        // Take max\n        long long int a = *max_element(heights.begin(), heights.end());\n        long long int b = *max_element(lengths.begin(), lengths.end());\n        \n        // Multiply and return\n        return (int)(a%mod*b%mod);\n    }\n};\n```\n\n***Code 2 :*** Compact, clean\n```\nclass Solution {\npublic:\n    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {\n        ios::sync_with_stdio(false);\n        cin.tie(NULL);\n        cout.tie(NULL);\n        function<int(vector<int>&,int)> getMax=[&](vector<int>& h,int hh){\n            sort(h.begin(),h.end());\n            int nh=h.size();\n            \n            int maxHeight=max(hh-h[nh-1],h[0]);\n            \n            for(int i=1;i<nh;++i)\n                maxHeight=max(maxHeight,h[i]-h[i-1]);\n            \n            return maxHeight;\n        };\n        return (int)((long)getMax(horizontalCuts,h)*getMax(verticalCuts,w)%1000000007);\n    }\n};\n```\n\n**Runtime:** 99 ms, faster than 56.44% of C++ online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.\n**Memory Usage:** 31.6 MB, less than 98.79% of C++ online submissions for Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts.\n\n**Time complexity :** O(NlogN)\n**Space Complexity :** O(1)\n\n\nHere\'s a quick proof why this is correct:\n\nWhy is `max(thickh) * max(thickv)` the correct answer? Well let\'s find the horizontal strip with the max height and then on the same strip with the widest vertical cut. We\'ll call the area formed `X` and we shall prove `X` has the max area.\n1. Clearly on the same horizontal strip, the place between the two widest vertical cuts has the max area.\n2. Now let\'s say there\'s actually another area NOT on the same horizontal strip with a bigger area than `X` Let\'s call that area `Y`. Since `Y` is not on the same horizontal\nstrip as `X`, `height(Y) < height(X)`. (Remember we found X on the horizontal strip with the max height.) And since `Area(Y) > Area(X)`, we have `width(Y) > width(X)`.\nBut then on the same horizontal strip where `X` sits, there\'s another area, let\'s call it `X\'`, that\'s on the same vertical strip as `Y` such that `width(X\') = width(Y) > width(X)`. But that contradicts our original assumption that `X was the area between two widest vertical cuts on its horizontal strip.`\nGiven 1. and 2. `X` must be have the max area.
['C', 'Sorting']