একটি পূর্ণসংখ্যা অ্যারে দেওয়া আছে। আমাদের সেই উপাদানগুলোর যোগফল বের করতে হবে যেগুলো সমねえ (contiguous) এবং যাদের যোগফল সর্বোচ্চ।
ডাইনামিক প্রোগ্রামিং ব্যবহার করে বর্তমান পদ পর্যন্ত সর্বোচ্চ যোগফল সংরক্ষণ করা হয়। এটি অ্যারেতে সমねえ উপাদানগুলোর যোগফল খুঁজে বের করতে সাহায্য করে।
ইনপুট এবং আউটপুট
ইনপুট: পূর্ণসংখ্যার একটি অ্যারে।
{-2, -3, 4, -1, -2, 1, 5, -3}
আউটপুট: সাবঅ্যারের সর্বোচ্চ যোগফল: ৭
অ্যালগরিদম
maxSum(array, n)
ইনপুট: মূল অ্যারে, অ্যারের আকার।
আউটপুট: সর্বোচ্চ যোগফল।
শুরু
tempMax := array[0]
currentMax = tempMax
i := 1 থেকে n-1 পর্যন্ত, করুন
currentMax = array[i] এবং (currentMax + array[i]) এর মধ্যে সর্বোচ্চ
tempMax = currentMax এবং tempMax এর মধ্যে সর্বোচ্চ
শেষ
tempMax ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
using namespace std;
int maxSum(int arr[], int n) {
int tempMax = arr[0];
int currentMax = tempMax;
for (int i = 1; i < n; i++) {
currentMax = max(arr[i], currentMax + arr[i]);
tempMax = max(tempMax, currentMax);
}
return tempMax;
}
int main() {
int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
int n = 8;
cout << "Maximum Sum of the Sub-array is: " << maxSum(arr, n);
}
আউটপুট
Maximum Sum of the Sub-array is: 7
