【最大子段和问题】 给定由n个整数组成的序列(a1, a2, …, an),最大子段和问题要求该序列形如 的最大值(1≤i≤j≤n)例如,序列(-20, 11, -4, 13, -5, -2)的最大子段和为: 20 c++语言实现
时间: 2024-02-25 15:58:59 浏览: 44
以下是基于Kadane算法的C++代码实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int maxSubArraySum(vector<int> arr) {
int max_so_far = arr[0]; // 初始化最大子段和为第一个元素
int max_ending_here = arr[0];
for (int i = 1; i < arr.size(); i++) {
max_ending_here = max(arr[i], max_ending_here + arr[i]); // 更新最大子段和
max_so_far = max(max_so_far, max_ending_here); // 更新全局最大子段和
}
return max_so_far;
}
int main() {
vector<int> arr = {-20, 11, -4, 13, -5, -2};
int max_sum = maxSubArraySum(arr);
cout << "最大子段和为:" << max_sum << endl;
return 0;
}
```
代码解释:
1. 定义了一个名为maxSubArraySum的函数,该函数接受一个vector<int>类型的数组作为参数,返回最大子段和的值。
2. 在函数中,我们使用两个变量max_so_far和max_ending_here来记录最大子段和的值,其中max_so_far记录全局最大子段和的值,max_ending_here记录以当前元素为结尾的最大子段和的值。
3. 通过一个循环遍历数组,对于每个元素,我们更新max_ending_here的值,如果更新后的值比原来的值大,就更新max_ending_here的值,否则不更新。同时,我们也需要更新全局最大子段和max_so_far的值。
4. 最后,函数返回max_so_far的值,即最大子段和的值。
5. 在main函数中,我们定义了一个测试数组,调用maxSubArraySum函数求解最大子段和,最后输出结果。