दिया गया कार्य एक दी गई बाइनरी स्ट्रिंग से एक उप-स्ट्रिंग ढूंढना और फिर शून्य और एक की संख्या के बीच अधिकतम अंतर ढूंढना है।
उदाहरण
इनपुट
str = "100100110"
आउटपुट
2
व्याख्या
पोजीशन 1 से 5 ("00100") की उप-सरणी में, शून्य और एक के बीच अंतर = 4 - 1 = 3 जो पाया जा सकने वाला अधिकतम है।
इनपुट
str = "00000"
आउटपुट
5
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है
- main() फ़ंक्शन में बाइनरी स्ट्रिंग संग्रहीत करने के लिए एक स्ट्रिंग str बनाएं। साथ ही स्ट्रिंग का आकार संग्रहीत करने के लिए एक चर int size आरंभ करें और दोनों को Max() फ़ंक्शन में पास करें।
- Max() फ़ंक्शन में पहले जांचें कि क्या सभी तत्व 1 हैं One() फ़ंक्शन को कॉल करके।
- One() फ़ंक्शन bool प्रकार का बनाएं और अंदर int O = 0 चर बनाएं।
- i = 0 से i < str.size() तक लूप करें और यदि str[i] == 1 तो चर O में 1 जोड़ें।
- लूप के बाहर, जांचें कि क्या (O == size)। यदि हां, तो true वापस करें।
- Max() फ़ंक्शन में वापस यदि One() फ़ंक्शन ने true वापस किया तो, उत्तर के रूप में -1 वापस करें।
- अन्यथा लंबाई ढूंढने के लिए आगे बढ़ें। एक सरणी int a[100] = { 0 } आरंभ करें।
- i = 0 से i < size तक लूप करें और a[i] = (str[i] == '0' ? 1 : -1) रखें और str के प्रत्येक तत्व की इस तरह जांच करें।
- लूप के बाहर, एक और सरणी int arr[100][3] आरंभ करें और memset(arr, -1, sizeof arr) का उपयोग करके इसके सभी तत्वों को -1 से बदलें और अंत में Length(a, str, size, 0, 0, arr) कॉल करें।
- Length() फ़ंक्शन में, पहले जांचें कि क्या (i >= size), यदि हां, तो इसका मतलब है कि स्ट्रिंग समाप्त हो गई है और 0 वापस करें।
- फिर जांचें कि क्या (arr[i][s] != -1)। यदि हां, तो इसका मतलब है कि स्थिति पहले ही गणना की जा चुकी है और arr[i][s] वापस करें।
- फिर जांचें कि क्या (s == 0)। यदि हां, तो arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), Length(a, str, size, i + 1, 0, arr)) वापस करें।
- अन्यथा arr[i][s] = max(a[i] + Length(a, str, size, i + 1, 1, arr), 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 (i >= size)
return 0;
// यदि पहले से गणना की गई।
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){
// जांचें कि क्या सभी तत्व 1 हैं
if (One(str, size))
return -1;
// लंबाई ढूंढना
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 फ़ंक्शन
int main(){
string str = "100100110";
int size = 9;
cout << Max(str, size);
return 0;
}
आउटपुट
3