原理

问题目标：寻找数组中连续子数组的最大和（最大子段和）。

• ​动态规划核心：定义 dp[i] 为以第 i 个元素结尾的最大子段和。
  • ​状态转移：
    • 若 dp[i-1] > 0，则 dp[i] = dp[i-1] + nums[i]（延续子段）。
    • 若 dp[i-1] ≤ 0，则 dp[i] = nums[i]（重新开始子段）。
  • ​公式：dp[i] = max(dp[i-1] + nums[i], nums[i])。
• ​全局最大值：在计算过程中记录所有 dp[i] 的最大值。

步骤

1. ​输入处理：
   • 读取数组长度 n 和数组元素。
2. ​初始化：
   • dp[0] = nums[0]（单个元素的最大子段和是它本身）。
   • result 初始化为 dp[0]。
3. ​动态规划更新：
   • 遍历数组，按状态转移方程计算每个 dp[i]。
   • 更新全局最大值 result。
4. ​输出结果：最终 result 即为最大子段和。

图示法表示步骤（示例输入 [-2, 1, -3, 4, -1, 2, 1, -5, 4]）

代码关键行注释

dp[0] = nums[0];  
// 初始化：单个元素的最大子段和是其本身  

result = dp[0];  
// 初始全局最大值  

dp[i] = max(dp[i-1] + nums[i], nums[i]);  
// 核心状态转移：选择延续子段或重新开始  

if (dp[i] > result) result = dp[i];  
// 实时更新全局最大值  

完整代码程序

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    vector<int> dp(n);
    if(n==0) cout<<0<<endl;
    dp[0]=nums[0];
    int result=dp[0];
    for(int i=1;i<n;i++){
        dp[i]=max(dp[i-1]+nums[i],nums[i]);
        if(dp[i]>result) result=dp[i];
    }
    cout<<result<<endl;

    return 0;
}

时间复杂度

• ​时间复杂度：O(n)，仅需一次遍历数组。
• ​空间复杂度：O(n)，用于存储 dp 数组。
  • ​优化点：可用变量代替 dp 数组，空间复杂度降至 O(1)。

总结

1. ​代码特点：
   • ​动态规划经典实现：逻辑清晰，直接反映问题的最优子结构。
   • ​正确处理边界：如全负数数组（输出最大单元素值）。
2. ​潜在问题：
   • ​空间冗余：若数组长度极大，dp 数组可能占用较多内存，可优化为仅保存前一个状态。
3. ​适用场景：
   • 实时数据流处理（逐个元素处理）。
   • 对时间复杂度要求严格的场景（如数据量百万级）。