洛谷题目链接：https://www.luogu.com.cn/problem/P1115#ide
本题使用了三种解法：双指针、前缀和、动态规划
前缀和解法：
前缀和解法采用的思想是，在遍历前缀和数组的同时，维护一个当前前缀和范围内的最小数值与最大区间和。从而实现，当前位置的前缀和数组元素 减去 维护的最小数值，得到当前位置的最大区间和。同时试图更新最大区间和（如果可以的话）。
#include <bits/stdc++.h>
using namespace std;
// 前缀和优化
const int N = 2e5 + 2;
int arr[N],pre[N];
int main(){
int n; cin>>n;
for(int i = 1; i<= n; i++){
cin>>arr[i];
pre[i] = pre[i – 1] + arr[i];
}
int mi = 0, ans = -1e9;
for(int i = 1; i <= n;i++){
int t = pre[i] – mi;
ans = max(ans, t);
mi = min(mi, pre[i]);
}
cout<<ans;
return 0;
}
首先输入数组元素，同时计算得到前缀和数组（前缀和数组即原数组下标1~i的数组元素总和）
for(int i = 1; i<= n; i++){
cin>>arr[i];
// 这里注意，因为前缀和数组的元素i需要用到元素i-1的值，那么开始元素设为0的话就会下标越界
pre[i] = pre[i – 1] + arr[i];
}
所以我们使用前缀和数组时需要将下标1设为起始位置。
int mi = 0, ans = -1e9;
这里我们维护一个当前元素前面的最小数值 mi ，和最大字段和 ans。
这里mi的作用是存储一个最小的pre数组中的元素，所以应该设置为0，代表子段是从下标1位置开始取的。后面如果有 < 0 的数会更新掉mi，代表从中间部分截取。
ans负责维护最大字段和的值，所以初值应该设置的非常小。
for(int i = 1; i <= n;i++){
int t = pre[i] – mi;
ans = max(ans, t);
mi = min(mi, pre[i]);
}
这部分循环枚举计算当前位置的最大字段和
首先计算当前区间的字段和
然后如果当前计算出的字段和超过了之前的最大字段和，进行更新
最后更新mi，如果当前的前缀和元素小于之前维护的最小数值mi，进行更新
（为什么能用pre[i] – mi，表示当前位置的最大字段和呢？ 首先设置区间左端点l， 右端点r，区间（l~r）的计算公式是 pre[l] – pre[l-1]。此时我们维护的mi恰好找的是在当前位置之前的最小的mi，这样减出来的结果也是最大的。于是得到了这个位置的最大子段和）
动态规划写法：
动态规划的思想是，维护一个存储当前位置最大字段和的数组dp。首先字段是连续的区间，所以dp数组的每一个元素需要考虑的就是是否需要和前面连起来。
然后我们需要着手设计动态规划的三个要素：状态设计、状态转移方程、边界条件。
首先状态设计部分，我们确定dp数组的含义是，dp[i] 表示 第i位的最大字段和。
状态转移方程部分，每个状态是由上一个状态确定的（这与递推的思想很像，两者的区别是动态规划会有一个取最优的行为）。第 i 位是否选择与前面接上取决于接上之后的值是否更大，也就是dp[i -1]是否大于0，于是可以确定dp[i]的值。
边界条件部分， 既然确定了每个状态的转移过程，那么我们就需要一个起点来保证状态转移方程的运行，也就是确定边界条件。根据转移方程不难看出每一位元素的确定需要前一个元素的参与，于是我们边界值就是第一个元素，因为第一个元素没有前驱元素。
整体代码如下：
// 动态规划
const int N = 2e5 + 2;
int arr[N], dp[N];
int main(){
int n; cin>>n;
for(int i = 0;i < n; i++) cin>>arr[i];
dp[0] = arr[0];
for(int i = 1; i < n; i++) dp[i] = max(dp[i – 1], 0) + arr[i];
int maxx = INT_MIN;
for(int i = 0; i< n; i++)maxx = max(maxx, dp[i]);
cout<<maxx;
return 0;
}
详解：
int arr[N], dp[N];
首先在全局区定义会默认初始化为0，并且全局可用，不需要在函数中形参列表中写出来了（当然开发中不要这么干），并且全局区可以开的数组大小比函数里（栈区）更大。
创建arr[N]数组用于存储输入的元素，dp[N]用于存储每个位置的最大字段和。N由题目中给的数据范围确定。
int n; cin>>n;
for(int i = 0;i < n; i++) cin>>arr[i];
常规写法，存储题目中给出的元素
dp[0] = arr[0];
设置边界条件，第一个位置他的最大字段和就是第一个元素
for(int i = 1; i < n; i++) dp[i] = max(dp[i – 1], 0) + arr[i];
枚举每个位置，确定第 i 个位置的最大字段和
首先需要判断前一个位置的最大字段和是否小于0，大于的话就加上前一个位置的值（也就是拼到一起），反之就是从当前元素开始重新开一段。
int maxx = INT_MIN;
for(int i = 0; i< n; i++)maxx = max(maxx, dp[i]);
cout<<maxx;
维护一个元素用于找dp数组中的最大值，找到的最大值就是整个数组的最大字段和
需要注意maxx需要取一个非常小的值才能被覆盖。常用的最小值INT_MIN，最大值INT_MAX
