最大子数组和可通过动态规划求解，定义currentSum为以当前元素结尾的最大和，maxSum记录全局最大值；状态转移方程为currentSum = max(nums[i], currentSum + nums[i])，每步更新maxSum；实现时仅需两个变量，时间复杂度O(n)，空间复杂度O(1)；初始化从nums[0]开始，遍历过程中持续更新currentSum与maxSum，最终返回maxSum；适用于包含负数的数组，能正确处理边界情况如空数组或单元素数组。
在C++中，使用动态规划求解最大子数组和是一个经典问题，通常称为“最大连续子数组和”或“Kadane算法”。核心思想是：每一步决策都保留以当前位置结尾的最大子数组和，从而逐步推导出全局最大值。
动态规划思路解析
定义状态：dp[i] 表示以第 i 个元素结尾的最大子数组和。由于只需要前一个状态，可以优化空间，只用一个变量记录当前最大和。
状态转移方程为：
dp[i] = max(nums[i], dp[i-1] + nums[i])
立即学习“C++免费学习笔记（深入）”；
即：要么从当前元素重新开始，要么将当前元素加入前面的子数组。
C++实现代码
以下是基于动态规划的简洁实现，时间复杂度 O(n)，空间复杂度 O(1)：
#include#include #include using namespace std; int maxSubArray(vector & 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 arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; cout << "最大子数组和为：" << maxSubArray(arr) << endl; return 0; }
关键点说明
• 初始化：maxSum 和 currentSum 都从 nums[0] 开始，确保处理负数数组。
• 状态更新：每一步判断是否延续之前的子数组，还是从当前点重新开始。
• 边界情况：空数组需单独判断；单元素数组也能正确返回结果。
• 空间优化：不需要完整 dp 数组，只需两个变量即可完成计算。
基本上就这些。这个方法高效且易于理解，适合面试和实际应用。
