最大子段和学习笔记

什么是最大子段和？

给定$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. 由前半段的部分和后半段的部分组成的序列相同

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$了，那么就要重新以他为开头建立一个子串。

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