#include <iostream>
#include <vector>
#include <climits>  // 提供INT_MIN，表示负无穷大
using namespace std;

const int N = 2e5 + 10;  // 数组最大长度
int arr[N];  // 存储输入的数组
int n;  // 数组实际长度

int main() 
{
    cin >> n;  // 读取数组长度
    for(int i = 0; i < n; i++)
        cin >> arr[i];  // 读取数组元素
    
    vector<int> dp(n);  // dp[i]表示以arr[i]结尾的连续子数组的最大和
    int max_num = INT_MIN;  // 全局最大和，初始化为负无穷大
    
    // 处理边界：第一个元素的最大子数组和就是它本身
    dp[0] = arr[0];
    max_num = max(max_num, dp[0]);  // 更新全局最大值
    
    // 从第二个元素开始遍历，计算每个位置的dp[i]
    for(int i = 1; i < n; i++)
    {
        // 状态转移：两种选择取较大值
        dp[i] = max(dp[i - 1] + arr[i], arr[i]);
        // 更新全局最大和
        max_num = max(max_num, dp[i]);
    }        
    
    // 输出全局最大和。这里的判断是冗余的，因为max_num至少会被初始化为dp[0]
    cout << (max_num == INT_MIN ? dp[0] : max_num) << endl;
    return 0;
}
  1. 初始化 max_num = INT_MIN：确保任何元素的值都能更新max_num，即使数组全为负数。
  2. 边界处理：dp[0] = arr[0]，因为以第一个元素结尾的子数组只有它本身。
  3. 状态转移的逻辑：若dp[i-1] > 0，则dp[i] = dp[i-1] + arr[i]（加入前面的子数组）。若dp[i-1] ≤ 0，则dp[i] = arr[i]（以自己为起点）。

然后可以是空间优化，不需要额外的 dp 数组，利用两个变量进行优化！

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

const int N = 2e5 + 10;  // 数组最大长度（预处理优化）
int arr[N];  // 存储输入的数组
int n;  // 数组实际长度

int main() 
{
    cin >> n;  // 读取数组长度
    for(int i = 0; i < n; i++)
        cin >> arr[i];  // 读取数组元素
    
    // a: 以当前元素结尾的连续子数组的最大和
    // b: 全局最大和
    int a = arr[0], b = arr[0];
    
    // 从第二个元素开始遍历，计算每个位置的最大子数组和
    for(int i = 1; i < n; i++)
    {
        // 状态转移：更新"以当前元素结尾的最大和"
        a = max(arr[i], a + arr[i]);
        // 更新全局最大和
        b = max(a, b);
    }        
    
    cout << b << endl;  // 输出全局最大和
    return 0;
}
  1. 变量初始化：a = arr[0]：处理边界情况，以第一个元素结尾的子数组只有它本身。b = arr[0]：初始全局最大值为第一个元素，确保即使数组全为负数也能正确返回最大值。
  2. 状态转移的逻辑：若 a > 0，则 a = a + arr[i]（加入前面的子数组）。若 a ≤ 0，则 a = arr[i]（以自己为起点）。