用分治法求出最大子段和的下标范围C++
时间: 2024-10-21 10:07:59 浏览: 13
分治法求解最大子段和问题通常涉及到Kadane's Algorithm,这是一种动态规划策略。在C++中,可以这样实现:
```cpp
#include <vector>
#include <climits>
// 函数用于找出数组中连续子数组的最大和及其起始和结束索引
std::pair<int, std::pair<int, int>> maxSubArraySum(const std::vector<int>& nums) {
int n = nums.size();
if (n <= 0)
return {0, {0, 0}};
// 初始化两个指针,left和right分别表示当前子数组的开始和结束
int left = 0, right = 0;
int curr_sum = nums[0], max_sum = nums[0];
int start_index = 0;
while (right < n) {
// 如果当前元素加上之前的sum大于0,说明添加当前元素更好
if (curr_sum + nums[right] > nums[right]) {
curr_sum += nums[right]; // 更新当前子数组的和
} else {
// 否则,从当前元素开始重新计算sum
curr_sum = nums[right];
start_index = right + 1; // 更新开始位置到当前元素
}
// 比较当前max_sum和curr_sum,更新结果
max_sum = std::max(max_sum, curr_sum);
right++;
}
// 返回最大和及其对应的起始和结束索引
return {max_sum, {start_index, start_index + max_sum - 1}};
}
int main() {
std::vector<int> nums{-2, 1, -3, 4, -1, 2, 1, -5, 4};
auto result = maxSubArraySum(nums);
std::cout << "Max Subarray Sum: " << result.first << "\n";
std::cout << "Start and End Indexes: (" << result.second.first << ", " << result.second.second << ")\n";
return 0;
}
```
这个函数`maxSubArraySum`会找到数组中具有最大和的连续子数组,并返回该子数组的和以及它的起始和结束索引。
阅读全文