এই সমস্যায়, আমাদের একটি অ্যারে এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল এমন একটি প্রোগ্রাম তৈরি করা যা c++ এ সর্বাধিক উপাদান হিসাবে k সহ অ-ওভারল্যাপিং সাবয়ারের দৈর্ঘ্যের সর্বাধিক যোগফল খুঁজে পাবে।
সমস্যা বর্ণনা - এখানে, আমাদের একটি অ্যারে এবং একটি পূর্ণসংখ্যা k আছে। আমাদের এই অ্যারে থেকে তৈরি করা যেতে পারে এমন সমস্ত সম্ভাব্য নন-ওভারল্যাপিং সাব-অ্যারে খুঁজে বের করতে হবে। এবং তৈরি করা সমস্ত সাবয়ারের দৈর্ঘ্য যোগ করুন।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − অ্যারে ={3, 7, 1, 2, 3, 1, 6, 3, 2, 5} k =3
আউটপুট − 7
ব্যাখ্যা − সর্বাধিক উপাদান 3 সহ অ-ওভারল্যাপিং সাবয়ারে:
{3} : length = 1
{1, 2, 3, 1} : length = 4
{3, 2} : length = 2
Sum of length = 1+4+2 = 7 এই সমস্যাটি সমাধান করার জন্য, আমরা অ্যারেটি অতিক্রম করব এবং কম এমন সমস্ত উপাদান খুঁজে বের করব এবং একটি দৈর্ঘ্য বজায় রাখব, যদি সাবয়ারে (উপাদানের স্ট্রিম) k থাকে তাহলে যোগফলের দৈর্ঘ্য যোগ করুন।
উদাহরণ
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
#include <iostream>
using namespace std;
int subArrayLengthSum(int arr[], int n, int k){
int lengthSum = 0;
int subarrayLength = 0;
int flag = 0;
for (int i = 0; i < n;) {
subarrayLength = 0;
flag = 0;
while (arr[i] <= k && i < n) {
subarrayLength++;
if (arr[i] == k)
flag = 1;
i++;
}
if (flag == 1)
lengthSum += subarrayLength;
while (arr[i] > k && i < n)
i++;
}
return lengthSum;
}
int main(){
int arr[] = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5};
int size = sizeof(arr) / sizeof(arr[0]);
int k = 3;
int ans = subArrayLengthSum(arr, size, k);
cout<<"The max sum of lengths of non-overlapping subarrays with "<<k<<" as max element is "<<ans;
return 0;
} আউটপুট
The max sum of lengths of non-overlapping subarrays with 3 as max element is 7
