समस्या कथन
इकाई और शून्य से मिलकर बनी एक स्ट्रिंग को देखते हुए। कार्य स्ट्रिंग के खंडों की अधिकतम लंबाई का पता लगाना है जैसे कि प्रत्येक खंड में 1 की संख्या 0 से अधिक हो
उदाहरण
यदि इनपुट स्ट्रिंग "10111000001011" है, तो उत्तर 12 इस प्रकार होगा -
- पहला खंड 7 10111000001011 लंबाई का है
- दूसरा खंड 5 10111000001011 लंबाई का है
- कुल लंबाई किसकी लंबाई है (सेगमेंट 1 + सेगमेंट 2) =(7 + 5) =12
एल्गोरिदम
- यदि प्रारंभ ==n तो 0 पर लौटें।
- आरंभ से n तक एक लूप चलाएं, प्रत्येक उप-सरणी के लिए n तक की गणना करें।
- यदि वर्ण 1 है तो 1 की संख्या बढ़ाएँ अन्यथा 0 की संख्या बढ़ाएँ।
- यदि 1 की संख्या 0 से अधिक है, तो अनुक्रमणिका (k+1) यानी अगली अनुक्रमणिका के लिए फ़ंक्शन को दोबारा कॉल करें और शेष लंबाई यानी k-start+1 जोड़ें।
- अन्यथा केवल अगली अनुक्रमणिका k+1 के लिए फ़ंक्शन को पुनरावर्ती रूप से कॉल करें।
- रिटर्न डीपी[शुरू]।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
int getSegmentWithMaxLength(int start, string str, int n, int dp[]) {
if (start == n) {
return 0;
}
if (dp[start] != -1) {
return dp[start];
}
dp[start] = 0;
int one = 0;
int zero = 0;
int k;
for (k = start; k < n; ++k) {
if (str[k] == '1') {
++one;
} else {
++zero;
} if (one > zero) {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp) + k - start + 1);
} else {
dp[start] = max(dp[start], getSegmentWithMaxLength(k + 1, str, n, dp));
}
}
return dp[start];
}
int main() {
string str = "10111000001011";
int n = str.size();
int dp[n + 1];
memset(dp, -1, sizeof(dp));
cout << "Maximum length of segment = " << getSegmentWithMaxLength(0, str, n, dp) << endl;
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है -
Maximum length of segment = 12