Question

C++大佬帮忙解释一下这段程序，最好是能有注释。评论区里告诉我，谢谢

题目背景
最大子段和问题是指：给出一段序列，选出其中连续且非空的一段使得这段和最大。

对于一个子段和a[l]+a[l+1]+...+a[r]，我们称a[l]为起点，a[r]为终点。

题目描述
本题中，我们给定一个长度为N的数组和一个分界点M，请求出起点a[l]在a[1],a[2],...a[M]之中，终点a[r]在a[M+1],a[M+2],...,a[N]之中的最大子段和。

输入输出格式
输入格式：
第一行是两个正整数N和M，N表示了序列的长度，M表示分界点。

第二行包含N个绝对值不大于10000的整数A[i]。

（注意，这意味着可能含有负数）

输出格式：
一个整数，为最大的子段和是多少。

输入输出样例
输入样例#1：
5 3
7 -7 9 -5 -5
输出样例#1：
4
输入样例#2：
7 5
0 2 1 8 0 7 -6
输出样例#2：
18
说明
对于40%的数据，有N<=2000

对于100%的数据，有2<=N<=200000，1<=M<N。

M下标从1开始计。

Answer 1

格式：

第一行是一个正整数N，表示了序列的长度。

第2行包含N个绝对值不大于10000的整数A[i]，描述了这段序列。

输出格式：

仅包括1个整数，为最大的子段和是多少。子段的最小长度为1。

枚举

最蠢的办法，枚举左端点和右端点，再求和，用一个max储存历史的最大值，就可以了。时间复杂度O(n3)。

View Code
在枚举的基础上，我们可以发现：求一个和为最大的子序列，那么作为任意一个子序列，若它的左端点是第i个元素，右端点是第j个元素，则它其中的元素之和可以表示为第1~j个元素和第1~i个元素之差。

这就是一个预处理。可以在枚举的基础上减少一些时间，但并不是最优，也是O(n2)。

分治

用分治求最大子段和应首先将这整个问题划分成规模更小的子问题，可以取中点，将这一个序列划分成长度相等的两个序列。对于此时的最大子段和，会出现3种情况，即：

1.最大子段和在第一个序列中，即在我们所取的中点左边。

2.最大子段和在第二个序列中，即在我们所取的中点右边；

3.最大子段和在第一个序列与第二个序列之间，即我们取的这个点被包含在这个子段中。这时，我们就应该继续以这个子段为基础，继续划分，知道不能划分为止。　　

(其实上面两种情况也是要划分的)(滑稽)

将3种情况的最大子段和合并，取三者之中的最大值就为问题的解。时间复杂度