একটি অ্যারে এবং একটি ইন্টিজার k দেওয়া আছে। k যেন ম্যাক্সিমাম এলিমেন্ট হয় এমন সব নন-ওভারল্যাপিং সাবঅ্যারে বের করে তাদের লেন্থের যোগফল বের করতে হবে।
উদাহরণ: array = {3, 7, 1, 2, 3, 1, 6, 3, 2, 5}, k = 3 -> আউটপুট: ৭
ব্যাখ্যা: নন-ওভারল্যাপিং সাবঅ্যারে যাদের ম্যাক্স এলিমেন্ট ৩: {3} (লেন্থ ১), {1,2,3,1} (লেন্থ ৪), {3,2} (লেন্থ ২)। যোগফল = ১+৪+২ = ৭।
সমাধান: অ্যারে ট্রাভার্স করিয়ে k-এর চেয়ে ছোট বা সমান এলিমেন্টের স্ট্রীম (subarray) বের করব। স্ট্রীমে k থাকলে তার লেন্থ যোগফলে যোগ করব। 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
