সমস্যা বিবৃতি
এক এবং শূন্য সমন্বিত একটি স্ট্রিং দেওয়া হয়েছে। কাজটি হল স্ট্রিং এর সেগমেন্টের সর্বোচ্চ দৈর্ঘ্য খুঁজে বের করা যাতে প্রতিটি সেগমেন্টে 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 এর জন্য শুধুমাত্র পুনরাবৃত্তভাবে ফাংশনটি কল করুন।
- 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
