最大子段和问题

lyc 收录于题目

2021-11-08 2021-11-08 约 1731 字预计阅读 4 分钟 - 条评论

最大子段和

问题：给定n个整数（可能为负数）组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整数均为负数时定义子段和为0，依此定义，所求的最优值为： Max{0,a[i]+a[i+1]+…+a[j]},1<=i<=j<=n 例如，当a[]=(-20,11,-4,13,-5,-2)时，最大子段和为20。

以上内容来自百度百科

思想1：递归思想

分析这个问题，我们可以这么想：我们把给定的数组搞一条中线出来，设它为mid吧，然后把它分成两部分，对于这个最大子段和，它有可能出现的地方有多少种情况呢?

出现在左边部分,也就是左边的最大子段和大于右边
出现在右边部分，和上面相反
出现在中间部分，也就是中线被夹在中间

那么，用二分的思想来做，我们是不是可以对左边同样执行上面的步骤，直到只有一个元素了，也就是到达了base case的地步了，这时候我就把这个值返回，然后走右边的。等到两边都走完了，我再看看中间这种情况，然后找出这三者当中大的那个返回给上一级。

我再细讲一下中间情况下是怎么处理的：

既然最大子段和出现再中间位置，那么是不是说，它有一部分数据在中线的左边，一部分数据出现在中线的右边呀？那么，我分别求出中线往左的数的和的最大值，以及中线往右的数的和的最大值，最后把它们加到一起，是不是就是我中间这种情况出现的最大子段和了？

好，那下面上代码看看：

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int max_sub_sum(int arr[], int l, int r) {
    if (l == r)
        return max(arr[l], 0);
    else {
        int mid = l + (r - l) / 2;
        int lres = max_sub_sum(arr, l, mid);      //找出左边最大的子段和
        int rres = max_sub_sum(arr, mid + 1, r);  //找出右边最大的子段和
        int lmax = 0, rmax = 0, sum = 0;
        for (int i = mid; i >= l; i--) {          //找出中线左边的数的和最大值
            sum += arr[i];
            lmax = max(sum, lmax);
        }
        sum = 0;
        for (int i = mid + 1; i <= r; i++) {      //中线右边的数的和最大值
            sum += arr[i];
            rmax = max(sum, rmax);
        }
        int midres = lmax + rmax;                 //两边加起来就是中间情况下的最大子段和
        return max(max(lres, rres), midres);
    }
}

时间复杂度分析

$T(n)=2T(\frac{n}{2})+2O(n)+O(1)$

由master公式，$a=2,b=2,d=1\to\log_ba=1=d$ 则时间复杂度：

$$T(n)=O(n*log{n})$$

不知道master的可以到时间复杂度这篇博文中进行查看，附上链接：{% post_link 算法基础/时间复杂度时间复杂度 %}

思想2：动态规划（补充）

在学了动态规划之后，老师还是给我们布置了这一道题，但是它叫最大子序和问题，刚开始我还以为是什么东西，后来想想，发现还是最大子段和问题，只不过现在它换了一种方法做，那就是动态规划。

我们看分治法可以发现，在它求解中间部分的最大子段和问题的时候，他还是用了枚举的这种方法，也就是说，它依然是重复执行了前面遍历过的东西。那我们可以想一种方法，怎么样才能尽可能大的利用我前面走过的数据用于后面的决策？

我们重新想这个问题，我们这个问题是不是相当于求长度为n的序列的最大子序和？

那我们拆分一下这个问题，或者说转换为更加一般的问题求解：

我们求长度为i 的最大子序和，或者说求已知序列前i 个数字的最大子序和。

那我们这样子想，求长度为i 的最大子序和，是不是可以利用前i-1个长度的序列的最大子序和以及当前位置上的数值a[i] 做出决策？我们设d[i]表示前i 个长度的序列的最大子序和，那么，像上面说的那样，求d[i]时可以利用d[i-1]做出决策，那么d[i] 有如下两种情况：

1
2


d[i]=d[i-1]+a[i] ,d[i-1]<0
d[i]=a[i]        ,d[i-1]>=0

这个也很好理解，如果前面的最大子序和为负数了，那$d[i-1]+a[i]<a[i]$，那我还不如那a[i]作为我当前的最大子序和呢！理解了之后，代码也很简单。

动态规划代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


/* 最大子序（段）和 */
#include <iostream>
using namespace std;
const int N=1e5+10;
int arr[N],d[N],n;
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    for(int i=1;i<=n;i++){
        if(d[i-1]<=0){
            d[i]=arr[i];
        }
        else{
            d[i]=d[i-1]+arr[i];
        }
    }
    int maxn=0;
    for(int i=0;i<=n;i++){
        maxn=max(maxn,d[i]);
    }
    cout << maxn;
    return 0;
}

时间复杂度:$O(n)$

改进

上面的内容有一个大前提，那就是所给的数组不能全部为负数，但是经过刷题，我发现别人的要求中是没有这一点的，所以，要进行改进，针对全部的数组，都可以返回一个最大子序和。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 最大子序（段）和 */
#include <iostream>
using namespace std;
const int N=1e6+10;
int arr[N],n;
int main(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> arr[i];
    }
    int pre=arr[0];
    int maxn=arr[0];
    for(int i=1;i<n;i++){
        pre=max(pre+arr[i],arr[i]);
        maxn=max(maxn,pre);
    }
    cout << maxn;
    return 0;
}

题目

洛谷：https://www.luogu.com.cn/problem/P1115

Leetcode: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/submissions/