কাদানের অ্যালগরিদম বাস্তবায়নের জন্য C++ প্রোগ্রাম

কাদানের অ্যালগরিদমটি পূর্ণসংখ্যার অ্যারে থেকে সর্বাধিক সাব্যারে যোগফল বের করতে ব্যবহৃত হয়। এখানে আমরা এই অ্যালগরিদম বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম নিয়ে আলোচনা করব।

অ্যালগরিদম

Begin
Function kadanes(int array[], int length):
   Initialize
   highestMax = 0
   currentElementMax = 0
   for i = 0 to length-1
      currentElementMax = max(array[i],currentElementMax + array[i])
      highestMax = max(highestMax, currentElementMax)
   return highestMax
End

উদাহরণ

#include<iostream>
using namespace std;
int kadanes(int array[],int length) {
   int highestMax = 0;
   int currentElementMax = 0;
   for(int i = 0; i < length; i++){
      currentElementMax =max(array[i],currentElementMax + array[i]) ;
      highestMax = max(highestMax,currentElementMax);
   }
   return highestMax;
}
int main() {
   cout << "Enter the array length: ";
   int l;
   cin >> l;
   int arr[l];
   cout << "Enter the elements of array: ";
   for (int i = 0; i < l; i++) {
      cin >> arr[i];
   }
   cout << "The Maximum Sum is: "<<kadanes(arr,l) << endl;
   return 0;
}

আউটপুট

Enter the array length: 7
Enter the elements of array:
-1
-2
-3
-4
-5
6
7
The Maximum Sum is: 13