প্রদত্ত কাজটি হল একটি প্রদত্ত বাইনারি স্ট্রিং থেকে একটি সাব-স্ট্রিং খুঁজে বের করা এবং তারপরে শূন্য এবং সংখ্যার মধ্যে সর্বাধিক পার্থক্য।
আসুন এখন বুঝতে পারি −
একটি উদাহরণ ব্যবহার করে আমাদের কী করতে হবেইনপুট
str = “100100110”
আউটপুট
2
ব্যাখ্যা
পজিশন 1 থেকে 5 ("00100") পর্যন্ত সাব-অ্যারেতে, জিরোস্যান্ডের মধ্যে পার্থক্য =4 – 1 =3 যা সর্বাধিক পাওয়া যেতে পারে।
ইনপুট
str = “00000”
আউটপুট
5
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
main() ফাংশনে str একটি স্ট্রিং তৈরি করুন বাইনারি স্ট্রিং সংরক্ষণ করতে। এছাড়াও আকার সংরক্ষণ করতে পরিবর্তনশীল int আকার শুরু করুন এর স্ট্রিং এবং উভয়কে ম্যাক্স()ফাংশনে পাস করুন।
-
Max() ফাংশনে প্রথমে One() ফাংশন কল করে সমস্ত উপাদান 1 কিনা তা পরীক্ষা করুন।
-
টাইপের বুলের One() ফাংশন তৈরি করুন এবং এর ভিতরে একটি পরিবর্তনশীল int O =0 তৈরি করুন।
-
i =0 থেকে i
-
লুপের বাইরে, পরীক্ষা করুন যদি (O ==আকার)। যদি তাই হয়, তাহলে সত্য ফিরে আসুন।
-
আবার Max() ফাংশনে ফিরে আসুন যদি One() ফাংশনটি সত্য হয়, তাহলে উত্তর হিসাবে -1 রিটার্ন করুন।
-
অন্যথায় দৈর্ঘ্য খুঁজে এগিয়ে যান. একটি অ্যারে int a[100] ={ 0 } শুরু করুন।
-
i =0 থেকে i<সাইজ পর্যন্ত লুপ করুন এবং a[i] =(str[i] =='0' ? 1 :-1) রাখুন এবং এইভাবে str এর প্রতিটি উপাদান পরীক্ষা করুন।
-
লুপের বাইরে, অন্য একটি অ্যারে int arr[100][3] শুরু করুন এবং মেমসেট (arr, -1, sizeof arr) ব্যবহার করে -1 দ্বারা এর সমস্ত উপাদান প্রতিস্থাপন করুন এবং অবশেষে দৈর্ঘ্য (a, str, size, 0, 0, arr) কল করুন।
-
Length() ফাংশনে, প্রথমে চেক করুন যদি (i>=সাইজ), যদি তাই হয়, তাহলে এর মানে স্ট্রিং বেশি হয়ে গেছে এবং 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 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;
} আউটপুট
3
