सी ++ में अधिकतम संख्या

मान लीजिए कि हमारे पास आयाम w x h के साथ एक मैट्रिक्स M है, जैसे कि प्रत्येक सेल का मान 0 या 1 है, और आकार l x l के M के किसी भी वर्ग उप-मैट्रिक्स में अधिकतम अधिकतम संख्या है। हमें मैट्रिक्स M में अधिकतम संभव संख्या ज्ञात करनी होगी।

इसलिए, यदि इनपुट w =3, h =3, l =2, maxOnes =1 जैसा है, तो आउटपुट 4 होगा जैसा कि 3*3 मैट्रिक्स में होता है, 2*2 सब-मैट्रिक्स में 1 से अधिक नहीं हो सकते हैं . सबसे अच्छा समाधान जिसमें 4 हैं -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=0

• n x n आकार का एक 2D सरणी वर्ग बनाएं

• इनिशियलाइज़ करने के लिए मैं :=0, जब मैं <ऊंचाई, अपडेट (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 <का आकार v और j

• वापसी रिट

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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