题目模型：给定一个序列 ,找出一段连续的区间 ，使得 最大，即经典的最大连续和问题。
各种做法
1、 级，是个人都会，暴力枚举i和j，再求和，代码不给出。
2、 级，也很简单，加个前缀和数组 即可去掉求和的这一重循环。代码同样不给出，80分。
3、 级，运用二分的思想，设 maxsum(i,j) 表示区间[,)中的最大连续和， 表示区间的中点。
那么，先求出 maxsum(mid,j) 与 maxsum(i,mid)。
然后，我们求出“经过mid点”的最大连续和：先找起点，再找终点
代码：
int maxsum(int l, int r)
{
int v, L, R, maxs, mid;
if (r - l == 1) return a[x]; //一个数字……你懂的(
mid = (l + r) / 2;
maxs = max(maxsum(l, mid), maxsum(mid, r)); //分治
//求出“经过Mid点”的最大连续和
v = 0, L = a[mid - 1];
for (int i = mid - 1; i >= l; i --) L = max(L, v += a[i]);
v = 0, r = a[mid];
for (int i = mid; i <= r; i ++) R = max(R, v += a[i]);
return max(maxs, L + R);//搞定
}
4. 级。
二分的做法很巧妙，也能AC，但是有一种比他简单粗暴还更快还更好写的代码（就是我的做法）
显然，在 的区间中，他的和就是 。
我们可以“扫描”一遍数组，用 记录遇到过的最小的 ，每次遇到新的 ，只需要计算他与 的差值，再更新 即可。
代码我在另一篇讨论里写了，所以不再Ctrl + C
完结撒花，感谢陪伴
共 7 条回复
简称：
是对的
我试试
/qq/se
但是我还是要%zqs
没看懂
%%%