सी ++ में बाइनरी स्ट्रिंग में शून्य और वाले का अधिकतम अंतर

कार्य को देखते हुए किसी दिए गए बाइनरी स्ट्रिंग से एक उप-स्ट्रिंग और फिर शून्य और एक की संख्या के बीच अधिकतम अंतर खोजना है।

आइए अब एक उदाहरण का उपयोग करके समझते हैं कि हमें क्या करना है -

इनपुट

str = “100100110”

आउटपुट

स्पष्टीकरण

उप-सरणी में स्थिति 1 से 5 ("00100") में, शून्य और वाले के बीच का अंतर =4 - 1 =3 जो अधिकतम पाया जा सकता है।

इनपुट

str = “00000”

आउटपुट

निम्नलिखित कार्यक्रम में उपयोग किया गया दृष्टिकोण इस प्रकार है

मुख्य () फ़ंक्शन में एक स्ट्रिंग बनाएं str बाइनरी स्ट्रिंग को स्टोर करने के लिए। आकार . को स्टोर करने के लिए परिवर्तनीय int आकार भी प्रारंभ करें स्ट्रिंग की और दोनों को अधिकतम () फ़ंक्शन में पास करें।
मैक्स () फ़ंक्शन में, पहले जांचें कि क्या सभी तत्व एक () फ़ंक्शन को कॉल करके 1 हैं।
बूल प्रकार का वन() फ़ंक्शन बनाएं और इसके अंदर एक चर int O =0 बनाएं।
i =0 से i
लूप के बाहर, जांचें कि क्या (ओ ==आकार)। अगर ऐसा है, तो सही लौटें।
मैक्स () फ़ंक्शन में वापस यदि वन () फ़ंक्शन सही लौटा, तो उत्तर के रूप में -1 लौटाएं।
अन्यथा लंबाई ज्ञात करने के लिए आगे बढ़ें। एक ऐरे को इनिशियलाइज़ करें a[100] ={ 0 }।
i =0 से i<आकार तक लूप करें और a[i] =(str[i] =='0' ? 1:-1) डालें और str के प्रत्येक तत्व को इस प्रकार जांचें।
लूप के बाहर, एक और सरणी int arr [100] [3] को इनिशियलाइज़ करें और इसके सभी तत्वों को -1 से बदलें memset(arr, -1, sizeof arr) का उपयोग करें और अंत में Length(a, str, size, 0, 0, arr) को कॉल करें।
Length() फ़ंक्शन में, पहले जांचें कि क्या (i>=size), यदि ऐसा है, तो इसका मतलब है कि स्ट्रिंग खत्म हो गई है और 0.
फिर जांचें कि क्या (गिरफ्तारी [i] [एस]! =-1)। अगर ऐसा है, तो इसका मतलब है कि राज्य की पहले से ही गणना की जा चुकी है और वापसी गिरफ्तारी [i][s]।
फिर जांचें कि क्या (एस ==0) है। यदि ऐसा है, तो वापसी एआर [i] [एस] =अधिकतम (ए [i] + लंबाई (ए, स्ट्र, आकार, आई +1, 1, एआर), लंबाई (ए, स्ट्र, आकार, आई + 1, 0 , गिरफ्तार));
अन्यथा वापसी गिरफ्तारी [i] [एस] =अधिकतम (ए [i] + लंबाई (ए, स्ट्र, आकार, आई + 1, 1, एआर), 0);

उदाहरण

#include <bits/stdc++.h>
using namespace std;
bool One(string str, int size){
   int O = 0;
   for (int i = 0; i < str.size(); i++)
      O += (str[i] == '1');
   return (O == size);
}
int Length(int a[], string str, int size,
int i, int s, int arr[][3]){
   // If string is over.
   if (i >= size)
      return 0;
      // If the already calculated.
   if (arr[i][s] != -1)
      return arr[i][s];
   if (s == 0)
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr),
      Length(a, str, size, i + 1, 0, arr));
   else
      return arr[i][s] = max(a[i] +
      Length(a, str, size, i + 1, 1, arr), 0);
}
int Max(string str, int size){
   // Checking if all elements are 1
   if (One(str, size))
      return -1;
      // Finding length
   int a[100] = { 0 };
   for (int i = 0; i < size; i++)
      a[i] = (str[i] == '0' ? 1 : -1);
      int arr[100][3];
      memset(arr, -1, sizeof arr);
   return Length(a, str, size, 0, 0, arr);
}
// main function
int main(){
   string str = "100100110";
   int size = 9;
   cout << Max(str, size);
   return 0;
}