একটি অ্যারে এবং সংখ্যা k দেওয়া থাকলে, কমপক্ষে kটি উপাদান বিশিষ্ট উপঅ্যারেটির সর্বোচ্চ যোগফল বের করতে হবে।
অ্যালগরিদম (Kadane's Algorithm вариেশন)
maxSum[i]= সূচকiপর্যন্ত শেষ হওয়া সর্বোচ্চ সাবঅ্যারে যোগফল।- প্রথম
kউপাদানের যোগফলsum-এ রাখুন। kথেকেn-1পর্যন্ত লুপ: স্লাইডিং উইন্ডো দিয়েsumআপডেট করুন।result = max(result, sum, sum + maxSum[i-k])।
সি++ ইমপ্লিমেন্টেশন
#include <bits/stdc++.h>
using namespace std;
int getMaxSum(int a[], int n, int k) {
vector maxSum(n);
maxSum[0] = a[0];
int currMax = a[0];
for (int i = 1; i < n; i++) {
currMax = max(a[i], currMax + a[i]);
maxSum[i] = currMax;
}
int sum = 0;
for (int i = 0; i < k; i++) sum += a[i];
int result = sum;
for (int i = k; i < n; i++) {
sum += a[i] - a[i - k];
result = max(result, sum);
result = max(result, sum + maxSum[i - k]);
}
return result;
}
int main() {
int a[] = {5, 3, 7, -5, 6, 2, 1};
int k = 6;
cout << getMaxSum(a, 7, k) << endl; // 19
return 0;
}
আউটপুট
19
