এই সমস্যায়, আমাদের একটি অ্যারে অ্যারে [] এবং একটি পূর্ণসংখ্যা k দেওয়া হয়েছে। আমাদের কাজ হল অ্যারের প্রতিটি Kth উপাদান নিয়ে সর্বাধিক যোগফল খুঁজে বের করা।
সমস্যার বিবরণ:আমাদের অ্যারের উপাদানগুলির সর্বাধিক যোগফল খুঁজে বের করতে হবে যাতে সেগুলি k সূচী আলাদা হয়। আমাদের যোগফল সর্বাধিক করতে হবে,
যোগফল =arr[i] + arr[i+k] + arr[i + 2*k] + …. arr[i + p*k], যেমন (i + p*k)
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
সমস্যার একটি সহজ সমাধান হল দুটি নেস্টেড লুপ ব্যবহার করে, বাইরেরটি অ্যারের প্রতিটি উপাদানের জন্য এবং ভিতরেরটি i থেকে প্রতিটি kth উপাদান নেওয়ার যোগফল বের করতে ব্যবহৃত হয়। যেমন sum =arr[i] + arr[i + k] + arr[i + 2*k] + … + arr[i + p*k] যেমন (i + p*k)
এবং সর্বোচ্চ পরিমাণ ফেরত দিন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
একটি সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম, ইনপুট
arr[] = {5, 3, −1, 2, 4, −5, 6}, k = 4 আউটপুট
9
ব্যাখ্যা
All sums of every kth element is
5 + 4 = 9
3 − 5 = −2
−1 + 6 = 5
2
4
−5
6
The maximum is 9
সমাধান পদ্ধতি
উদাহরণ
#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
