最大子段和:动态规划算法c++

最大子段和是一个经典的算法问题，它的标是在一个给定的整数数组中找到一个连续子数组，使得该子数组的元素之和最大。动态规划是解决这个问题的常用方法之一。

以下是使用动态规划算法解决最大子段和问题的C++代码示例：

#include <iostream>
#include <vector>
using namespace std;

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    
    int maxSum = nums[0];  // 记录当前最大子段和
    int curSum = nums[0];  // 记录当前子段和
    
    for (int i = 1; i < n; i++) {
        // 如果当前子段和为负数，则舍弃之前的子段，从当前元素重新开始计算子段和
        curSum = max(curSum + nums[i], nums[i]);
        // 更新最大子段和
        maxSum = max(maxSum, curSum);
    }
    
    return maxSum;
}

int main() {
    vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int result = maxSubArray(nums);
    cout << "最大子段和为: " << result << endl;
    
    return 0;
}

上述代码中，我们使用两个变量`maxSum`和`curSum`来记录当前的最大子段和和当前的子段和。遍历整个数组，对于每个元素，我们判断当前子段和是否为负数，如果是负数，则舍弃之前的子段，从当前元素重新开始计算子段和；否则，将当前元素加入到当前子段和中。同时，我们更新最大子段和的值。最终返回`maxSum`即为最大子段和。