পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়। আমাদের সংলগ্ন সমস্ত উপাদানের যোগফল খুঁজে বের করতে হবে। যার যোগফল সবচেয়ে বড়, সেটি আউটপুট হিসেবে পাঠানো হবে।
ডাইনামিক প্রোগ্রামিং ব্যবহার করে আমরা বর্তমান টার্ম পর্যন্ত সর্বোচ্চ যোগফল সংরক্ষণ করব। এটি অ্যারের সংলগ্ন উপাদানগুলির যোগফল খুঁজে পেতে সহায়তা করবে৷
Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is : 7 অ্যালগরিদম
maxSum(অ্যারে, n)
ইনপুট − প্রধান অ্যারে, অ্যারের আকার।
আউটপুট - সর্বোচ্চ যোগফল।
Begin tempMax := array[0] currentMax = tempMax for i := 1 to n-1, do currentMax = maximum of (array[i] and currentMax+array[i]) tempMax = maximum of (currentMax and tempMax) done return tempMax End
উদাহরণ
#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++ ) { //find the max value
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
