একটি অ্যারে এবং একটি সংখ্যা k দেওয়া আছে। দৈর্ঘ্য k এর সাবঅ্যারেগুলোর মধ্যে সর্বাধিক (অথবা ন্যূনতম) যোগফল বের করতে হবে।
উদাহরণ
ইনপুট: arr = {55,43,12,76,89,25,99}, k = 2
আউটপুট: 165 (সাবঅ্যারে {76,89}, ইনডেক্স ৩ ও ৪)
অ্যালগরিদম: স্লাইডিং উইন্ডো (O(n))
- প্রথম
kএলিমেন্টের সম =maxSum। - উইন্ডো এক ধাপ ডানে স্লাইড করুন: নতুন এলিমেন্ট যোগ করুন, পুরনো এলিমেন্ট বিয়োগ করুন।
curr_sum += arr[i] - arr[i-k]।maxSum = max(maxSum, curr_sum)আপডেট করুন।
C++ প্রোগ্রাম
#include <iostream>
using namespace std;
int findMaxSumSubarray(int arr[], int n, int k) {
if (n < k) {
cout << "Invalid";
return -1;
}
int maxSum = 0;
for (int i = 0; i < k; i++) maxSum += arr[i];
int curr_sum = maxSum;
for (int i = k; i < n; i++) {
curr_sum += arr[i] - arr[i-k];
maxSum = max(maxSum, curr_sum);
}
return maxSum;
}
int main() {
int arr[] = {55,43,12,76,89,25,99};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
cout << "The sum of subarray with max sum of size " << k << " is " << findMaxSumSubarray(arr, n, k);
return 0;
}
আউটপুট
The sum of subarray with max sum of size 2 is 165
ন্যূনতম যোগফল বের করতে
maxSum-কে minSum এ রিপ্লেস করুন এবং max-কে min দিয়ে রিপ্লেস করুন।
কমপ্লেক্সিটি
- টাইম:
O(n)— প্রতিটি এলিমেন্ট একবার প্রসেস হয়। - স্পেস:
O(1)— এক্সট্রা অ্যারে লাগে না।
ব্রুট-ফোর্স (O(n×k))
প্রতিটি সাবঅ্যারের জন্য লুপ চালিয়ে সম বের করুন। বড় n,k-এ ধীর।
প্রায়োগিক টিপস
k > nহলে ইনভ্যালিড হ্যান্ডল করুন।- নেগেটিভ নাম্বার থাকলে
maxSumইনিশিয়ালাইজINT_MINদিয়ে করুন। - সাবঅ্যারের ইনডেক্সও জানতে চাইলে
startIdxট্র্যাক রাখুন।
