C++-এ বাইনারি স্ট্রিং-এ শূন্য এবং একের ম্যাক্সিমাম পার্থক্য

দেওয়া কাজ হচ্ছে একটি বাইনারি স্ট্রিং-এ থেকে একটি সাব-স্ট্রিং বের করা এবং তারপর শূন্য এবং একের সংখ্যার ম্যাক্সিমাম পার্থক্য বের করা।

উদাহরণ দিয়ে বুঝি −

ইনপুট

str = "100100110"

আউটপুট

ব্যাখ্যা

পজিশন ১ থেকে ৫-এ সাব-অ্যারে ("00100")-এ, শূন্য এবং একের পার্থক্য = ৪ - ১ = ৩ যা সর্বোচ্চ পাওয়া যায়।

ইনপুট

str = "00000"

আউটপুট

নিচের প্রোগ্রামে ব্যবহৃত পদ্ধতি নিম্নরূপ

main() ফাংশনে একটি স্ট্রিং str তৈরি করা হয় বাইনারি স্ট্রিং সংরক্ষণের জন্য। এছাড়া int size ভেরিয়েবল স্ট্রিং-এর size সংরক্ষণের জন্য এবং দুটোই Max() ফাংশনে পাস করা হয়।
Max() ফাংশনে প্রথমে চেক করা হয় সব এলিমেন্ট ১ কিনা One() ফাংশন কল করে।
One() ফাংশন bool টাইপের তৈরি করা হয় এবং এর ভিতরে int O = 0 ভেরিয়েবল।
i = 0 থেকে i< str.size() পর্যন্ত লুপ করে যদি str[i] == 1 হয় তবে O-এ ১ যোগ।
লুপের বাইরে, চেক করা হয় if(O == size)। যদি সত্য হয় তবে true রিটার্ন।
Max() ফাংশনে ফিরে, যদি One() ফাংশন true রিটার্ন করে, তবে -1 রিটার্ন করা হয় উত্তর হিসেবে।
অন্যথায় দৈর্ঘ্য বের করতে आगे বড়ুন। int a[100] = { 0 } অ্যারে ইনিশিয়ালাইজ।
i = 0 থেকে i< size পর্যন্ত লুপ করে a[i] = (str[i] == '0' ? 1 : -1) রাখা হয় এবং স্ট্রিং-এর প্রতিটি এলিমেন্ট চেক।
লুপের বাইরে, আরেকটি অ্যারে int arr[100][3] এবং এর সব এলিমেন্ট -1 দিয়ে রিপ্লেস করা হয় memset(arr, -1, sizeof arr) এবং শেষে Length(a, str, size, 0, 0, arr) কল।
Length() ফাংশনে, প্রথমে চেক করা হয় if (i >= size), যদি সত্য হয় তবে স্ট্রিং শেষ এবং ০ রিটার্ন।
তারপর চেক করা হয় if (arr[i][s] != -1)। যদি সত্য হয় তবে স্টেট ইতিমধ্যে ক্যালকুলেটেড এবং arr[i][s] রিটার্ন।
তারপর চেক করা হয় if(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 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; 
}