题目模型:给定一个序列 ,找出一段连续的区间 ,使得 最大,即经典的最大连续和问题。
各种做法
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
没看懂
%%%