C++ এ সর্বাধিক সংখ্যা

ধরুন আমাদের কাছে একটি ম্যাট্রিক্স M আছে যার ডাইমেনশন w x h আছে, যেমন প্রতিটি কক্ষের মান 0 বা 1 আছে, এবং l x l আকারের M-এর যেকোনো বর্গক্ষেত্র সাব-ম্যাট্রিক্সে সর্বাধিক maxOnes সংখ্যা রয়েছে। আমাদের ম্যাট্রিক্স M এর সম্ভাব্য সর্বাধিক সম্ভাব্য সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, ইনপুট যদি হয় w =3, h =3, l =2, maxOnes =1, তাহলে আউটপুট হবে 4 যেমন একটি 3*3 ম্যাট্রিক্সে, কোন 2*2 সাব-ম্যাট্রিক্সে 1 টির বেশি হতে পারে না . সর্বোত্তম সমাধান যার 4টি আছে তা হল −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• ret :=0

• n x n

  আকারের একটি 2D অ্যারে বর্গ করুন

• আরম্ভ করার জন্য i :=0, যখন i <উচ্চতা, আপডেট (i 1 দ্বারা বাড়ান), করবেন −

  • j শুরু করার জন্য :=0, যখন j <প্রস্থ, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −

    • sq[i mod n, j mod n] 1 দ্বারা বাড়ান

• একটি অ্যারে v

  সংজ্ঞায়িত করুন

• আরম্ভ করার জন্য i :=0, যখন i

  • j শুরু করার জন্য :=0, যখন j করুন

    • v

      এর শেষে sq[i, j] ঢোকান

• অ্যারে v কে বিপরীত ক্রমে সাজান

• আরম্ভ করার জন্য i :=0, j :=0, যখন i

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maximumNumberOfOnes(int width, int height, int n, int maxOnes) {
      int ret = 0;
      vector < vector <int> > sq(n, vector <int>(n));
      for(int i = 0; i < height; i++){
         for(int j = 0; j < width; j++){
            sq[i % n][j % n]++;
         }
      }
      vector <int> v;
      for(int i = 0; i < n; i++){
         for(int j = 0; j < n ; j++){
            v.push_back(sq[i][j]);
         }
      }
      sort(v.rbegin(), v.rend());
      for(int i = 0, j = 0; i < v.size() && j < maxOnes; i++, j++){
         ret += v[i];
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.maximumNumberOfOnes(3,3,2,1));
}

ইনপুট

3, 3, 2, 1

আউটপুট

4