最大子序和问题可通过动态规划高效求解，定义currentSum表示以当前元素结尾的最大和，maxSum记录全局最大值，状态转移方程为currentSum = max(nums[i], currentSum + nums[i])，每步更新maxSum，最终返回maxSum。代码实现中仅用两个变量实现O(1)空间复杂度，时间复杂度O(n)，适用于大规模数据处理，且可推广至最大子矩阵等问题。
在C++中，使用动态规划求解“最大子序和”问题是一种高效且经典的方法。该问题要求在一个整数数组中找出连续子数组，使其元素之和最大。
问题描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（至少包含一个元素），返回其最大和。
例如：
输入：[-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
动态规划思路
定义状态 dp[i] 表示以第 i 个元素结尾的最大子数组和。
状态转移方程：
dp[i] = max(nums[i], dp[i-1] + nums[i])
含义是：要么从当前元素重新开始，要么将当前元素加到前面的子序列上。
立即学习“C++免费学习笔记（深入）”；
由于只需要前一个状态，可以只用一个变量代替整个数组，实现空间优化。
C++ 实现代码
以下是使用动态规划实现的完整 C++ 代码：
#include <iostream>#include <vector>
#include <algorithm>
using namespace std;
int maxSubArray(vector<int>& nums) {
if (nums.empty()) return 0;
int maxSum = nums[0]; // 记录全局最大和
int currentSum = nums[0]; // 记录以当前元素结尾的最大和
for (int i = 1; i < nums.size(); ++i) {
currentSum = max(nums[i], currentSum + nums[i]);
maxSum = max(maxSum, currentSum);
}
return maxSum;
}
int main() {
vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
cout << "最大子序和为: " << maxSubArray(nums) << endl;
return 0;
}
算法特点与优化
时间复杂度：O(n)，只需遍历一次数组。
空间复杂度：O(1)，仅使用两个变量存储状态。
这种方法避免了暴力枚举所有子数组（O(n²)），也比分治法更简洁易懂。
核心思想是：每一步做出局部最优选择，最终得到全局最优解。
基本上就这些。掌握这个模式后，也能推广到类似问题，比如最大子矩阵和等。
