C++-এ কেক কাটায় সর্বোচ্চ এরিয়া বের করা

উচ্চতা h এবং প্রস্থ w ওয়ালা একটি কেক আছে। হরিজন্টাল কাট horizontalCuts এবং ভার্টিকেল কাট verticalCuts দেওয়া আছে। কাট করার পর সর্বোচ্চ আকারের টুকরোর এরিয়া বের করতে হবে (মডুলো ১০⁹+৭)।

ইনপুট: h=5, w=4, horizontalCuts=[1,2,4], verticalCuts=[1,3] → আউটপুট: 4

সমাধানের ধাপগুলো:

দুই অ্যারে সর্ট করব
শুরুতে ০ এবং শেষে h/w যোগ করব
সাবশেষ কাটের ম্যাক্স গ্যাপ বের করব (হরিজন্টালে a, ভার্টিকেলে b)
mul(a, b) % MOD রিটার্ন করব

উদাহরণ

নিচের কোডটি দেখুন −

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
typedef long long int lli;

class Solution {
public:
    lli mul(lli a, lli b) {
        return ((a % mod) * (b % mod)) % mod;
    }
    int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) {
        sort(hh.begin(), hh.end());
        sort(vv.begin(), vv.end());
        hh.insert(hh.begin(), 0);
        hh.push_back(h);
        vv.insert(vv.begin(), 0);
        vv.push_back(w);
        int a = 0, b = 0;
        for (int i = 1; i < hh.size(); i++) {
            a = max(a, hh[i] - hh[i - 1]);
        }
        for (int i = 1; i < vv.size(); i++) {
            b = max(b, vv[i] - vv[i - 1]);
        }
        return mul(a, b);
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,4}, v1 = {1,3};
    cout << (ob.maxArea(5, 4, v, v1));
}

ইনপুট

5,4,{1,2,4}, {1,3}