实施Kadane算法的C ++程序
Kadane的算法用于从整数数组中找出最大子数组和。在这里，我们将讨论一个实现该算法的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
热门推荐
10 医院探望朋友祝福语简短
11 毕业祝福语简短女朋友
12 春节虎年爸妈祝福语简短
13 儿童毕业祝福语 简短6
14 开工仪式横幅祝福语简短
15 孩子日常祝福语大全简短
16 清晨寄语诗句祝福语简短
17 结婚送亲认亲祝福语简短
18 虎年喝酒拜年祝福语简短