题目描述
给出一段序列，选出其中连续且非空的一段使得这段和最大。
输入描述
第一行是一个正整数 N ( 1 ≤ N ≤ 200000 ) ，表示了序列的长度。
接下来的 N 行包含 N 个绝对值不大于 10000 的整数 A [ i ] ，描述了这段序列。
输出描述
仅包括 1 个整数，为最大的子段和是多少，子段的最小长度为 1 。
样例输入
7
2
-4
3
-1
2
-4
3
样例输出
4
Hint
Origin: Sidney
Edit by stdKonjac in 2020
解题思路:
关于求子区间求和的问题，现在已经有很多套路，比如线段树和树状数组，因为这俩都是通过子区间划分后自定向下形成的树。但是毕竟是动态规划专题，还是不要背模板了。
说到划分，最著名的题就是整数划分问题，只是整数划分问题是从一个整数划到区间长度=1-n，而现在这个问题是从区间求和返回整数，相当于一个逆过程，
那么划分嘛，反过来就是归并，总体还是分治思想啊，所以，先复习一下分治法最有名的归并排序算法，
贴个链接：https://www.cnblogs.com/KID-yln/p/12636211.html
和归并一样，现在有两种思路，
- 第一种直接对区间划分，整体使用搜索递归，自顶向下，得到划分的区间脚标，然后返回一个求和，最好是能实现之前小期间的和能被后来的大区间利用到
- 第二种直接规定区间长度可为1-n，利用循环，仿照非递归实现的归并算法，每次得到脚标的起点和终点然后求和，具体优化可以仿照滑动窗口
因为是动态规划—递推专题，先说一下第二种做法：
如果用滑动窗口思路：
规定一个窗口大小从1-n的窗口，每次移动一个位置就一加一减，
进一步最好区间长度i从大到小遍历，并且把第i项第一个求和存下来，后面使用，
运算次数不超过O（n^2）,假设CPU运算次数为10^(-10)s一次，总耗时大概不会超过1s，有点勉强，可以试一试
（依照CPU i5 8400循环做 i-- ; 10亿次大概要1.2秒左右（10 0000 0000 一次减 1 减 10亿次到 0为止，该时间为循环延时时间+运算时间，循环延时时间占大头）
试了以下，运气很好，过了，
，不到100ms，不知道是不是cpu比较快
以下为代码：
1 #include <iostream> 2 #include <cstdio> 3 //#include <cstring> 4 #include <algorithm> 5 //#include <numeric> 6 using namespace std; 7 typedef long long ll; 8 const int M=2*1e5+10; 9 int n; 10 11 ll a[M]; 12 13 ll sum=0; 14 ll S(int from,int to) { 15 ll t=0; 16 for(int i=from; i<=to; i++)t+=a[i]; 17 return t; 18 } 19 20 void f() { 21 int n1=n; 22 ll sum1=S(1,n); 23 sum=sum1; 24 while(n1) { 25 int l=0; 26 int r=1+n1-1; 27 sum1-=a[r]; 28 ll ans=sum1; 29 while(r<=n) { 30 ans-=a[l]; 31 ans+=a[r]; 32 sum=max(sum,ans); 33 //printf("%lld ",ans); 34 l++; 35 r++; 36 } 37 //puts(""); 38 n1--; 39 } 40 printf("%lld ",sum); 41 } 42 43 44 45 int main() { 46 scanf("%d",&n); 47 for(int i=1; i<=n; i++)scanf("%lld",&a[i]); 48 a[0]=0; 49 f(); 50 51 52 return 0; 53 }
那这个思路改写成递推式是什么呢？这和设置变量有关
假设区间长度为 len ，起点为 i ，设和为dp【i】【len】，有
dp【i】【len】=dp【i-1】【len】-a【i-1】+a【i-1+len】
其中 a【i-1】=dp【i-1】【1】。所以有
dp【i】【len】=dp【i-1】【len】-dp【i-1】【1】+dp【i-1+len】【1】
dp【i】【len-1】=dp【i】【len】-dp【i-1+len】【1】
如果规定区间起点为 l ，终点为 r，设和为dp【l】【r】，1《l《r《n，分别以1-n个元素为起点，向外扩散，
区间从小到大变换，
dp【l】【r】=dp【l+1】【r-1】+dp【l】【l】+dp【r】【r】
区间如果从大到小
dp【l】【r】=dp【l-1】【r】-dp【l-1】【l-1】=dp【l】【r+1】-dp【r+1】【r+1】
个人觉得还是设置长度len，起点 i 为变量更加好一点，因为不用再次计算l-r
现在回头来说一下第一种做法：
如果直接递归，主要可以利用循环1-n，内套一个栈，设置栈深，每种情况都重新算一次，
总共有n（n+1）/2次求和，运算次数达到了Σ（n-i）*i => O（n^3）看这个数量级为200000，指定TE，
那么想要优化就需要简化运算次数，至少需要利用到之前的求和，保存之前的求和值作为节点，那其实就是建—线段树OR树状数组—然后求某些分支节点的和，
其实这也是分治，只不过是把分治的内容化成了一棵树，数量级约为O（n*logn）；
（占个坑，后面补上树状数组/线段树的做法）