সমস্যা বিবরণ
শুধু ০ এবং ১ দিয়ে গঠিত একটি স্ট্রিং দেওয়া আছে। কাজ হলো স্ট্রিংয়ের সেগমেন্টের সর্বোচ্চ দৈর্ঘ্য বের করা যাতে প্রতিটি সেগমেন্টে ১-এর সংখ্যা ০-এর চেয়ে বেশি থাকে।
উদাহরণ
ইনপুট স্ট্রিং যদি “10111000001011” হয়, তবে উত্তর হবে ১২ নিচেরভাবে −
- প্রথম সেগমেন্টের দৈর্ঘ্য ৭: 10111000001011
- দ্বিতীয় সেগমেন্টের দৈর্ঘ্য ৫: 10111000001011
- মোট দৈর্ঘ্য = (সেগমেন্ট ১ + সেগমেন্ট ২) = (7 + 5) = 12
অ্যালগরিদম
- যদি start == n হয় তবে 0 রিটার্ন করুন।
- start থেকে n পর্যন্ত একটি লুপ চালিয়ে প্রতিটি সাব-অ্যারে için হিসাব করুন।
- যদি ক্যারেক্টার ১ হয় তবে ১-এর কাউন্ট বাড়ান, অন্যথায় ০-এর কাউন্ট বাড়ান।
- যদি ১-এর কাউন্ট ০-এর চেয়ে বেশি হয়, তবে রিকার্সিভলি ফাংশনটি (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
