একটি ইন্টিজার অ্যারে দেওয়া আছে। আমাদের কন্টিগুয়াস এলিমেন্টগুলোর যোগফল বের করতে হবে। যেটির যোগফল সর্বোচ্চ, সেটিই আউটপুট হবে।
ডাইনামিক প্রোগ্রামিং ব্যবহার করে আমরা বর্তমান টার্ম পর্যন্ত সর্বোচ্চ যোগফল স্টোর করব। এটি অ্যারেতে কন্টিগুয়াস এলিমেন্টগুলোর যোগফল বের করতে সাহায্য করবে।
Input: An array of integers. {-2, -3, 4, -1, -2, 1, 5, -3} Output: Maximum Sum of the Subarray is : 7অ্যালগরিদম
maxSum(array, 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
উদাহরণ
#includeusing 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
