C++ में 0 और 1 के सेगमेंट की अधिकतम लंबाई

समस्या कथन

एक स्ट्रिंग दी गई है जिसमें केवल 0 और 1 हैं। कार्य स्ट्रिंग के सेगमेंट की अधिकतम लंबाई ढूंढना है जैसे कि प्रत्येक सेगमेंट में 1 की संख्या 0 से अधिक हो।

उदाहरण

यदि इनपुट स्ट्रिंग "10111000001011" है तो उत्तर 12 होगा -

• पहला सेगमेंट लंबाई 7 का है 10111000001011
• दूसरा सेगमेंट लंबाई 5 का है 10111000001011
• कुल लंबाई (सेगमेंट 1 + सेगमेंट 2) की लंबाई = (7 + 5) = 12 है

एल्गोरिदम

• यदि start == n तो 0 लौटाएं।
• start से n तक लूप चलाएं, n तक प्रत्येक सबऐरे के लिए गणना करें।
• यदि वर्ण 1 है तो 1 की गिनती बढ़ाएं अन्यथा 0 की गिनती बढ़ाएं।
• यदि 1 की गिनती 0 से अधिक है, तो इंडेक्स (k+1) यानी अगले इंडेक्स के लिए फंक्शन को रिकर्सिवली कॉल करें और शेष लंबाई यानी k-start+1 जोड़ें।
• अन्यथा केवल अगले इंडेक्स k+1 के लिए फंक्शन को रिकर्सिवली कॉल करें।
• dp[start] लौटाएं।

उदाहरण

#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