最大子段和学习笔记

最大子段和学习笔记

什么是最大子段和?

给定$n$个整数(可以为负数)组成的序列$a_1,a_2,…,a_n$,求该序列连续的字段和最大值。显然如果都是负数最大值可以为0。

解决方案1

暴力枚举开始位置$i$和终止位置$j$,对每一种可能性计算和。

复杂度$O(n^3)$

解决方案2

使用前缀和优化,保存$\sum_{i=1}^{j-1}a[i]$的结果。

复杂度$O(n^2)$

解决方案3

采用分治策略优化复杂度。

将给定序列$a$分成长度两段子序列$a[1,n/2],a[n/2+1,n]$,分别求出这两段的最大子段和,而总序列的最大子段和有三种情况

  1. 和前半段相同
  2. 和后半段相同
  3. 由前半段的部分和后半段的部分组成的序列相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int MaxSubSum(vector<int> ve,int l,int r){
int sum = 0;
if(l==r) return max(ve[l],0);
int mid = (l+r)>>1;
int lm = MaxSubSum(ve,l,mid);
int rm = MaxSubSum(ve,mid+1,r);
int ls = 0;int lefts = 0;
for(int i=mid;i>=l;i--){
lefts += ve[i];
ls = max(ls,lefts) //遍历更新最大值
}
int rs = 0;int rights = 0;
for(int i=mid+1;i<=r;i++){
rights += ve[i];
rs = max(rs,rights);
}
sum = ls + rs;
sum = max(sum,max(lm,rm));
return sum;
}

复杂度$O(nlogn)$

解决方案4

动态规划。

  • 设置$dp[i] = max(dp[i-1]+a[i],a[i])$,$dp[i]$表示以$i$为结尾的最长子串的和。
  • 对于每一个$a[i]$如果之前的最大子串小于$0$了,那么就要重新以他为开头建立一个子串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int MaxSubSum(vector<int> ve,int n,int& l,int& r){
int sum = -INF;int mmax = -INF;
int L=0;int R = 0;
for(int i=0;i<n;i++){
if(sum < 0){
sum = ve[i];
L = R = i;
}else{
sum += ve[i];
R ++;
}
if(mmax < sum){
mmax = sum;
l = L;r = R;
}
}
return mmax;
}

复杂度$O(n)$

解决方案5

最大子段的左右两个数字必定为正数,最左边数字

reference:https://blog.csdn.net/zhong36060123/article/details/4381391