最大连续和

1、暴力求解 O（n3）

int maxsum = a[1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int sum = 0;
for(int k = i; k <= j; k++) {
sum += a[k];
}
maxsum = max(maxsum, sum);
}
}

2、预处理暴力求解 O（n2）

int maxsum = a[1];
s[0] = 0;
//最大连续和等于两个前缀和之差
for(int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
for(int i = 1; i <= n; i++) {
for(int j = i; j <= n; j++) {
maxsum = max(maxsum, s[j] - s[i - 1]);
}
}

3、分治法求解 O（nlogn）

int MaxSubSum(int l, int r) {
int sum = 0;
if(l == r) { //基本情况，只有一个元素
return a[l];
}
int mid = (l + r) >> 1;
int lsum = MaxSubSum(l, mid); //左半部分
int rsum = MaxSubSum(mid + 1, r); //右半部分
// 求包含左半部分最右元素的最大和
int s1 = 0, ls = 0;
for(int i = mid; i >= l; i--) {
ls += a[i];
s1 = max(s1, ls);
}
// 求包含右半部分最左元素的最大和
int s2 = 0, rs = 0;
for(int i = mid + 1; i <= r; i++) {
rs += a[i];
s2 = max(s2, rs);
}
//取三者最大值
sum = s1 + s2;
sum = max(sum, max(lsum, rsum));
return sum;
}

4、动态规划 O（n）

// 状态转移方程
//sum[i] = max(sum[i - 1] + a[i], a[i]); // sum[i]记录以a[i]为子序列末端的最大连续和
int sum = 0, maxsum = 0;
for(int i = 1; i <= n; i++) {
if(sum > 0) {
sum += a[i];
} else {
sum = a[i];
}
maxsum = max(maxsum, sum);
}

最后

以上就是繁荣水池为你收集整理的最大连续和的全部内容，希望文章能够帮你解决最大连续和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。