### Leetcode #1465: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

#### Link to the Problem

Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

#### Thought Process

Each cut in the cake, divides the cake into pieces with certain height and certain width. We want to maximize the area, so the best piece would the one with maximum height among all pieces and maximum width among all pieces.

So the only task for us is to find what would be the height and width of each piece after all cuts and then find the piece with maximum height and width. Area of the piece is simply the multiplication of the height and the width.

#### Algorithm

1. Get maximum height of a piece among all pieces.
1. Sort the horizontal cuts array so that each horizontal cut would result in pieces of certain height.
2. Find the max among them.
2. Similarly for the width.
3. Multiply height and width.

#### Code

 class Solution { const int mod = (1e9)+7; // As the question expects. int getMax(int length, vector &cuts) { sort(cuts.begin(), cuts.end()); // Sort so that we will easily get the thickness // of each piece after cutting it. int n = cuts.size(); int maxCut = max(length-cuts[n-1], // Thickness of the last piece. cuts[0]); // Thickness of the first piece. for (int i=1; i& h, vector& w) { long maxHeight = getMax(height, h); long maxWidth = getMax(width, w); return (int)(maxHeight * maxWidth % mod); } };
view raw Leetcode_1465.cpp hosted with ❤ by GitHub

Is there anything that is still unclear? Let me know in the comments and I can elaborate further.

Don’t forget like & share the post, and subscribe to the blog to get notifications whenever solution to a new problem is added.

Happy Coding!

#### Similar Problems

Leetcode #492: Construct the Rectangle