力扣53题：贪心策略与动态规划的完美联姻 三行代码映射算法精髓

题目理解

在数字的海洋中寻找最具价值的珍珠链：当我们面对一个可能包含正负数的数组时，寻找连续子数组的和最大值就像在波动的股票曲线中捕捉最佳投资时段。问题的核心在于如何处理可能降低总和的负值元素——是忍痛割裂历史累积，还是负重前行等待转机？这是对决策智慧的终极考验。

算法解析

本解法通过‌动态规划的压缩空间技巧‌，仅用两个变量完成状态转移：

1‌.sum的自我进化‌：每一步决策时，若当前元素前的子数组和为正（可贡献增益），则将其与当前元素相加；若为负（拖累后续），则果断开启新子数组

2‌.maxsum的守望者角色‌：如同登山向导的里程碑标记，始终记录着攀登过程中的最高海拔值

3‌.智能重启机制‌：max(sum,0)的表达式将动态规划的转移方程 max(nums[i], sum+nums[i]) 隐式转换为更简洁的数学形式

该算法遍历数组时如同扫描雷达：

1.初始时将sum和maxsum设为第一个元素的值

2.从第二个元素开始，通过sum = nums[i] + max(sum,0)实现状态转移

3.每次更新后立即检查是否需要更新全局最大值

时间复杂度O(n)高效处理大数据量，空间复杂度O(1)达至最优。

代码及注释

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];      // 初始化当前子数组和（动态规划的压缩状态）
        int maxsum = sum;       // 全局峰值记录器
        
        // 从第二个元素开始探索所有可能的子数组终点
        for(int i = 1; i < nums.size(); i++) {
            // 决策核心：历史积累若为正则保留，为负则清零重启
            sum = nums[i] + max(sum, 0);  // 等价于 max(nums[i], sum+nums[i])
            
            // 实时校验是否刷新历史最高记录
            if(sum > maxsum) {    
                maxsum = sum;  // 攀上新高峰时更新旗帜
            }
        }
        
        return maxsum;  // 返回探索到的最高海拔值
    }
};