首页 > 代码库 > 最大连续和的方法总结
最大连续和的方法总结
最大连续和的方法总结
第一种：暴力。复杂度O（n^3)。用两个循环枚举起点和终点，然后中间再放一个循环，计算这个起点到终点的连续和。
伪代码：
max = -INF;
s[maxn];
for i in range(1, len):
for(j in range(i, len)):
sum = 0;
for (k in range(i, j)):
sum += s[k];
else:
max = Max(max, sum);
else:;
else:
return max;
第二种：预处理 + 暴力枚举起点终点。复杂度O（n^2)。和第一个类似，只是一开始用sum[i]，来储存从1到i的连续和。这样就可以去掉第三层的循环，直接用sum[end] - sum[begin]得到。
伪代码：
max = -INF;
s[maxn], sum[maxn];
sum[0] = 0;
for i int range(1, len):
sum[i] = sum[i - 1] + s[i];
else:;
for i in range(1, len):
for j int range（i, len):
max = Max(max, sum[j] - sum[i - 1]);
else:;
else:
return max;
第三种：分治法， 复杂度O(n*log(n))。思路是将长度为len的序列划分左右两个左闭右开的区间[l,m) [m, r)，然后递归求出左边的区间的最大连续和，再求出右边的最大连续和，最后在求出跨中点m的最大连续和，这个区间的最大连续和就在这三者之中。将每个区间都划分成子问区间，直到区间只有一个数的时候停止。注意：两个区间不能同时拥有同一个元素，这样在后面的区间再划分的时候会出错（划分成单个元素区间的时候会发现每个元素都多了一个），这也是要左闭右开区间的原因。
伪代码：
l = 1;
r = len + 1；
function maxsum (l, r)
if r - l == 1: return s[l];
m = (l + r) / 2;
//左子区间
maxLp = maxsum(l, m);
//右子区间
maxRp = maxsum(m, r);
max = Max(maxLp, maxRp);
//中间的跨越中点m的区间
sumLp = s[m - 1];
sum = 0;
for i in range(m - 1, l)://i--
sum += s[i];
maxLp = Max(maxLp, sum);
else:;
sumRp = s[m];
sum = 0;
for i in range(m, r - 1)://i++
sum += s[i];
maxRp = Max(maxRp, sum);
else:;
return Max(max, maxRp + maxLp);
end function
第四种：累积遍历算法(1)，复杂度O(n).从左到右用一个Sum变量累计，当Sum<0的时候就令Sum = 0,再去加上后面的数,并且在这个遍历的过程中记录下Sum的最大值。换句话说：用这个Sum将这个序列分段，如果前面的连续和比0还小的话，那么加上后面的数倒还没有后面的数自己作为开头的连续和大，所以就让Sum = 0.这样才可能产生比前面的连续和更大的值。
伪代码：
s[maxn];
max = sum = s[1];
for i in range(2, len):
if sum < 0:
sum = s[i];
else:
sum += s[i];
max = Max (max, sum);
else: return max;
第五种：累积遍历算法(2)，复杂度O(n).同样也是用一个变量Sum来累计，只是这里用一个MinPart来保存前面从1开始的最小的连续和。因为这个序列的所有值的和是确定的，那么只要取得了前面的最小连续和，因为总值是固定的，后面的就是最大的连续和，也就是遍历过程中Sum - MinPart的最大值。
伪代码；
s[maxn];
MinPart = sum = 0;//注意开头可能是正数
max = s[1];
for in range(1, len):
sum += s[i];
max = Max (sum - MinPart);
MinPart = Min (MinPart, sum);
else: return max;
第六种：动态规划，复杂度O(n)。和第四种的想法是类似的，只是这里是开一个sum[maxn]的数组。状态转移方程：sum[i] = Max(sum[i - 1] + s[i], s[i])；
伪代码：
sum[maxn],s[maxn];
max = sum[1] = s[1];//只有一个数的情况下只能取这个数
for in range(2, len):
sum[i] = Max (sum[i - 1] + s[i], s[i])
max = Max (max, sum[i]);
else: return max;
接下来是UVA507的题目的四种解法，因为前两种比较简单而且放在这题会超时就不写了。这题需要给出上下界的。
分治法
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4 + 5;
int n, s[maxn];
struct Ans {
int v, l, r;
Ans () {}
Ans (int v, int l , int r) : v(v), l(l), r(r){}
void set (int v, int l, int r) {
this->v = v;
this->l = l;
this->r = r;
}
};
Ans maxsum (int l, int r) {
if (r - l == 1)
return Ans(s[l], l, l);
Ans max_sum;
int m = l + (r - l)/2;
Ans Lmax = maxsum(l, m);
Ans Rmax = maxsum(m, r);
if (Lmax.v > Rmax.v)
max_sum = Lmax;
else if (Lmax.v < Rmax.v)
max_sum = Rmax;
else {
if (Lmax.r - Lmax.l < Rmax.r - Rmax.l)
max_sum = Rmax;
else
max_sum = Lmax;
}
Ans Lp(s[m - 1], m - 1, m - 1), Rp(s[m], m, m);
int tmp = 0;
for (int i = m - 1; i >= l; i--) {
tmp += s[i];
if (tmp >= Lp.v)
Lp.set(tmp, i, m - 1);
}
tmp = 0;
for (int i = m; i < r; i++) {
tmp += s[i];
if (tmp >= Rp.v)
Rp.set(tmp, m, i);
}
Ans Center(Lp.v + Rp.v, Lp.l, Rp.r);
if (Center.v > max_sum.v)
max_sum = Center;
else if (Center.v == max_sum.v) {
int dis1 = Center.r - Center.l;
int dis2 = max_sum.r - max_sum.l;
if (dis1 > dis2 || (dis1 == dis2 && Center.l < max_sum.l))
max_sum = Center;
}
return max_sum;
}
int main () {
int T;
scanf ("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf ("%d", &n);
for (int i = 0; i < n - 1; i++)
scanf ("%d", &s[i]);
Ans result = maxsum(0, n - 1);
// printf ("%d\n", result.v);
if (result.v < 0)
printf ("Route %d has no nice parts\n", cas);
else
printf ("The nicest part of route %d is between stops %d and %d\n", cas, result.l + 1, result.r + 2);
}
return 0;
}
累计遍历法(1):
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4 + 5;
int n, s[maxn];
int solve (int& l, int& r) {
int Max_num, sum;
int tmp;
l = r = tmp = 1; //border
Max_num = sum = s[0];
for (int i = 1; i < n - 1; i++) {
if (sum < 0) {
sum = s[i];
tmp = i + 1;
} else
sum += s[i];
if (sum > Max_num) {
Max_num = sum;
l = tmp;
r = i + 1;
} else if (sum == Max_num) {
if (r - l < i + 1 - tmp || ((r - l) == (i + 1 - tmp) && tmp < l)) {
l = tmp;
r = i + 1;
}
}
}
return Max_num;
}
int main () {
int T, l, r;
scanf ("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d", &n);
for (int i = 0; i < n - 1; i++)
scanf ("%d", &s[i]);
int ans = solve(l, r);
// printf ("%d\n", ans);
if (ans < 0)
printf ("Route %d has no nice parts\n", cas);
else
printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);
}
return 0;
}
累积遍历法(2):
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4 + 5;
int n, s[maxn];
int solve (int& l, int& r) {
int Min_sum, sum, Max_sum;
int tmp;
tmp = 0; //border
l = r = 1;
sum = Min_sum = 0;
Max_sum = s[0];
for (int i = 0; i < n - 1; i++) {
sum += s[i];
if (sum - Min_sum >= Max_sum) {
if (sum - Min_sum > Max_sum) {
Max_sum = sum - Min_sum;
l = tmp + 1;
r = i + 1;
} else if (sum - Min_sum == Max_sum) {
if (i - tmp > r - l) {
l = tmp + 1;
r = i + 1;
}
}
}
if (sum < Min_sum) {
Min_sum = sum;
tmp = i + 1;
}
}
return Max_sum;
}
int main () {
int T, l, r;
scanf ("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf("%d", &n);
for (int i = 0; i < n - 1; i++)
scanf ("%d", &s[i]);
int ans = solve(l, r);
// printf ("%d\n", ans);
if (ans < 0)
printf ("Route %d has no nice parts\n", cas);
else
printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);
}
return 0;
}
动态规划：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e4 + 5;
int n, s[maxn], sum[maxn];
int solve (int& l, int& r) {
int Max_sum, tmp;
Max_sum = sum[0] = s[0];
l = r = tmp = 1;
for (int i = 1; i < n - 1; i++) {
if (sum[i - 1] + s[i] < s[i]) {
sum[i] = s[i];
tmp = i + 1;
} else
sum[i] = sum[i - 1] + s[i];
//max
if (Max_sum <= sum[i]) {
if (Max_sum < sum[i]) {
Max_sum = sum[i];
l = tmp;
r = i + 1;
} else if (Max_sum == sum[i] && (i + 1 - tmp > r - l)) {
l = tmp;
r = i + 1;
}
}
}
return Max_sum;
}
int main () {
int T, l, r;
scanf ("%d", &T);
for (int cas = 1; cas <= T; cas++) {
scanf ("%d", &n);
for (int i = 0; i < n - 1; i++)
scanf ("%d", &s[i]);
int ans = solve(l, r);
if (ans < 0)
printf ("Route %d has no nice parts\n", cas);
else
printf ("The nicest part of route %d is between stops %d and %d\n", cas, l, r + 1);
}
return 0;
}
感谢GG大神：参考博客
最大连续和的方法总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。