এই সমস্যায়, আমাদের একটি অ্যারে arr[] এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। আমাদের কাজ হলো অ্যারেতে প্রতি K-এন্টিম উপাদান নিয়ে সর্বোচ্চ যোগফল খুঁজে বের করা।
সমস্যা বিবরণ
আমাদের অ্যারে উপাদানগুলোর সর্বোচ্চ যোগফল বের করতে হবে যাতে সেগুলো k ইনডেক্স অন্তরে থাকে। অর্থাৎ যোগফল ম্যাক্সিমাইজ করতে হবে:
sum = arr[i] + arr[i+k] + arr[i + 2*k] + ... + arr[i + p*k], যাতে (i + p*k) < n
উদাহরণ
ইনপুট
arr[] = {5, 3, -1, 2, 4, -5, 6}, k = 4
আউটপুট
9
ব্যাখ্যা
প্রতি k-এন্টিম উপাদানের সব যোগফল: 5 + 4 = 9 3 - 5 = -2 -1 + 6 = 5 2 4 -5 6 সর্বোচ্চ হলো 9
সমাধানের পদ্ধতি
একটি সহজ সমাধান হলো দুটি নেস্টেড লুপ ব্যবহার করা। বাহ্যিক লুপ অ্যারের প্রতিটি উপাদানের জন্য এবং অভ্যন্তরীণ লুপ i থেকে প্রতি k-এন্টিম উপাদান নিয়ে যোগফল বের করতে। তারপর সর্বোচ্চ যোগফল ফেরত দেয়া।
C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)
#include <iostream>
using namespace std;
int findMaxSumK(int arr[], int n, int K){
int maxSum = -1000;
for (int i = 0; i < n; i++) {
int current_Sum = 0;
for (int j = i; j < n; j += K)
current_Sum = current_Sum + arr[j];
maxSum = max(maxSum, current_Sum);
}
return maxSum;
}
int main(){
int arr[] = {5, 3, -1, 2, 4, -5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << "The maximum sum taking every Kth element in the array is " << findMaxSumK(arr, n, K);
return (0);
}
আউটপুট
The maximum sum taking every Kth element in the array is 13
অপ্টিমাইজড পদ্ধতি (সাফিক্স সম ব্যবহার করে)
#include <iostream>
using namespace std;
int findMaxSumK(int arr[], int n, int K) {
int maxSum = -1000;
int suffSum[n] = {0};
for (int i = n - 1; i >= 0; i--) {
if (i + K < n)
suffSum[i] = suffSum[i + K] + arr[i];
else
suffSum[i] = arr[i];
maxSum = max(maxSum, suffSum[i]);
}
return maxSum;
}
int main(){
int arr[] = {5, 3, -1, 2, 4, -5, 6};
int n = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << "The maximum sum taking every Kth element in the array is " << findMaxSumK(arr, n, K);
return (0);
}
আউটপুট
The maximum sum taking every Kth element in the array is 13
