【题目来源】
洛谷：P1115 最大子段和 - 洛谷
【题目描述】
给出一个长度为 \(n\) 的序列 \(a\)，选出其中连续且非空的一段使得这段和最大。
【输入】
第一行是一个整数，表示序列的长度 \(n\)。
第二行有 \(n\) 个整数，第 \(i\) 个整数表示序列的第 \(i\) 个数字 \(a_i\)。
【输出】
输出一行一个整数表示答案。
【输入样例】
7
2 -4 3 -1 2 -4 3
【输出样例】
4
【算法标签】
《洛谷 P1115 最大子段和》 #动态规划DP# #贪心# #递推# #分治# #前缀和#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 200005; // 定义最大数组长度int n; // 数组元素个数
int a[N]; // 存储原始数组
int f[N]; // 动态规划数组，f[i]表示以a[i]结尾的最大子数组和
int ans = -1e9; // 存储全局最大子数组和，初始化为极小值int main()
{// 输入数组元素个数cin >> n;// 输入数组元素for (int i = 1; i <= n; i++){cin >> a[i];}// 动态规划：计算以每个位置结尾的最大子数组和for (int i = 1; i <= n; i++){// 状态转移方程：// 以a[i]结尾的最大子数组和 = max(前一个最大子数组和 + a[i], 单独取a[i])f[i] = max(f[i - 1] + a[i], a[i]);}// 遍历所有位置，找到全局最大值for (int i = 1; i <= n; i++){ans = max(ans, f[i]);}// 输出最大子数组和cout << ans << endl;return 0;
}
【运行结果】
7
2 -4 3 -1 2 -4 3
4