कादाने एल्गोरिदम का उपयोग इंटीजर्स के ऐरे से अधिकतम सबएरे सम खोजने के लिए किया जाता है। यहां हम इस एल्गोरिदम को कार्यान्वित करने के लिए एक C++ प्रोग्राम पर चर्चा करेंगे।
एल्गोरिदम
Begin
Function kadanes(int array[], int length):
इनिशियलाइज़
highestMax = 0
currentElementMax = 0
for i = 0 से 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
कादाने एल्गोरिदम O(n) समय में अधिकतम सबएरे सम खोजता है। यह नेगेटिव नंबर्स को हैंडल करता है वर्तमान मैक्स को रीसेट करके जब यह नेगेटिव हो जाता है। नोट: यदि सभी नंबर नेगेटिव हैं, तो यह एल्गोरिदम 0 लौटाता है (खाली सबएरे)। सभी नेगेटिव के लिए अधिकतम एलिमेंट लौटाने के लिए, highestMax को INT_MIN से इनिशियलाइज़ करें और currentElementMax को array[0] से।