C++最大子数组和问题及Kadane算法实现

这个问题是一个典型的 **最大子数组和** 问题（Kadane 算法）。 ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; int maxSubarraySum(const vector<int>& nums) { int currentSum = 0; int maxSum = nums[0]; // 初始化为第一个元素的值 for (int num : nums) { currentSum = max(num, currentSum + num); maxSum = max(maxSum, currentSum); } return maxSum; } int main() { vector<int> gains = {1, -2, 3, 5, -1, 2}; // 示例输入 int result = maxSubarraySum(gains); cout << "最大总增益为: " << result << endl; return 0; } ``` 这段代码使用 Kadane 算法在线性时间内解决问题。它遍历数组，维护两个关键变量： - `currentSum`：以当前位置结尾的最大子数组和 - `maxSum`：全局最大子数组和 每个位置选择“从当前元素重新开始”或者“延续之前的子数组”中较大的一个。初始将 `maxSum` 设为第一个元素的值，确保数组全为负数时也能正确返回最大值。 ######[AI问答 | 289点数解答 | 2026-05-16 22:07:13]