用c++编写给定由n个整数组成的序列(a1, a2, …, an),求该序列形如 累加ak 的子段和的最大值。
时间: 2024-10-10 19:04:57 浏览: 12
在C++中,我们可以使用滑动窗口技术(Sliding Window Technique)来解决这个问题,这种算法常用于数组和字符串的相关问题中,比如最大子数组和、最长公共子串等。下面是一个基本的解决方案:
```cpp
#include <vector>
#include <climits>
int maxSubArraySum(std::vector<int>& nums, int n) {
if (n == 0) return 0;
int cur_sum = nums[0], max_sum = nums[0];
// 初始化左边界和右边界
int left = 0, right = 1;
while (right < n) {
// 更新当前子数组和
cur_sum += nums[right];
// 如果新的子数组和大于最大子数组和,更新最大值
if (cur_sum > max_sum) {
max_sum = cur_sum;
}
// 当当前元素不再参与计算时,移除它
cur_sum -= nums[left];
// 移动左边界
left++;
// 右边界右移
right++;
}
return max_sum;
}
int main() {
std::vector<int> nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int n = nums.size();
int result = maxSubArraySum(nums, n);
std::cout << "子段和的最大值为: " << result << std::endl;
return 0;
}
```
上述代码定义了一个`maxSubArraySum`函数,它维护一个左右边界,从左向右遍历数组,每次将右端点增加一个元素,同时将左端点移向右,如果新添加的元素使得和变大,就更新最大和。最后返回的就是整个过程中找到的最大累加和。