বৃহত্তম সমষ্টি সংলগ্ন সাবাররে

পূর্ণসংখ্যার একটি অ্যারে দেওয়া হয়েছে৷ আমাদের সমস্ত উপাদানের যোগফল খুঁজে বের করতে হবে যা সংলগ্ন, যার যোগফল সবচেয়ে বড়, যা আউটপুট হিসাবে পাঠানো হবে।

ডাইনামিক প্রোগ্রামিং ব্যবহার করে আমরা বর্তমান টার্ম পর্যন্ত সর্বাধিক যোগফল সংরক্ষণ করব। এটি অ্যারের সংলগ্ন উপাদানগুলির যোগফল খুঁজে পেতে সহায়তা করবে৷

ইনপুট এবং আউটপুট

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

উদাহরণ

#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