最大子段和

发表于 | 分类于

问题描述

给定由n个整数(可能有负整数)组成的序列($a_1,a_2,…,a_n$),要求该序列形如$\sum_{k=i}^{j}a_k$的最大值($1\leq i \leq j \leq n$)。 例如，序列(-20,11,-4,13,-5,-2)的最大子段和为$\sum_{k=2}^{4}a_k=20$。

问题解析

这里我们要考虑两点：

  • 1.保证子段最大
  • 2.且要保证子段是连续的（这句相当于废话，既然是子段，肯定是连续的）

最简单的方法（暴力枚举）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void maximumSum(int arr[]){
    int k = 0,n= arr.length;
    int sum = 0;
    int maxValue = -10000;
    int left = 0,right = 0;
    for(int l=0;l<n;l++){
        for(int r=l;r<n;r++){
            for (int i=l;i<=r;i++){
                sum+=arr[i];//主要循环语句
            }
            if (sum>maxValue){
                maxValue=sum;
                left = l;
                right = r;
            }
            sum = 0;
        }
    }
    System.out.println("最大和为"+maxValue);
    System.out.println("下标从"+left+"到"+right);
}

暴力枚举比较简单，就是将所有情况一一列出，每次循环都进行比较，取最大的那一段。

可以计算一下时间复杂度。







可以看出该算法是O($n^3$)

暴力求解升级版

暴力求解的方式是一一列出每种可能性，而上面那种算法在计算每种可能的和的时候多用了一层循环， 所以我们可以对上面的算法进行改进，只需要两个for循环就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void maximumSumPro(int[] arr){
    int n= arr.length;
    int sum = 0;
    int maxValue = -10000;
    int left = 0,right = 0;
    for(int i=0;i<n;i++){
        sum = 0;
        for(int j=i;j<n;j++){
            sum+=arr[j];
            if (sum>maxValue){
                maxValue=sum;
                left=i;
                right=j;
            }
        }
    }
    System.out.println("最大和为"+maxValue);
    System.out.println("下标从"+left+"到"+right);
}

该算法时间复杂度为O($n^2$)

动态规划

动态规划的定义：动态规划适用于子问题不是独立的情况，也就是各个子问题包含公共的子子问题，在这种情况下，若用分治法会做许多不必要的工作，即重复的求解公共的子子问题。（之后也会讲解分治法） 上面的升级版其实也算是动态规划的一个简易版，我们就是要把这些重复的步骤给剔除掉。 可以通过总结得出一个递推公式

我们要从$Sum[i-1]+arr[i]和arr[i]$中选出一个最大的值，而Sum[i-1]加上arr[i]却没有arr[i]大，说明arr[i]比Sun[i-1]大，而且Sum[i-1]是个负值，所以我们就可以直接舍去之前的Sum[i-1]，从当前的arr[i]开始继续往下累加。结合下图与代码进行理解。
在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void dynamicProgramming(int arr[]){
    int n = arr.length;
    int maxValue = -10000;
    int sum = 0;
    int left=0,right=0;
    for (int i=0;i<n;i++){
        if (sum+arr[i]>arr[i]){
            sum+=arr[i];
        }else {
            sum = arr[i];
            left = i;
        }
        if (sum>maxValue){
            maxValue = sum;
            right = i;
        }

    }
    System.out.println("最大和为"+maxValue);
    System.out.println("下标从"+left+"到"+right);
}

分治法

采用分治法，可能会出现三种情况($a_1,…,a_n$)：

  • 1.最大子段和在$a_1,…,a_n$的左半边，即$a_1,…,a_{n/2}$
  • 2.最大子段和在$a_1,…,a_n$的右半边，即$a_{n/2},…,a_1$
  • 3.最大子段和在$a_1,…,a_n$的左右半边之间，即$\sum_{k=i}^{j}{a_k},且1 \leq i \leq \frac{n}{2},\frac{n}{2} \leq j\leq n$

求解思路

使用分治法就是将问题分成若干个子问题，最后在合并。 举几个例子可能会更加容易理解：

  • 1.数组[2,-1]
左 右
2 -1

左边最大的是2，右边最大的是-1，横跨左右半边的是$2+(-1)=1$，所以最大子段和是2

  • 2.数组[1,2,3,4]
1    2    3    4
左 右
1 2 3 4
左 右 左 右
1 2 3 4

首先将问题分成四个子问题，结合代码会更容易理解。
当数组划分到不能再划分就会执行

1
2
3
4
if (left==right){
    sum = arr[left];
}
return sum;

这时就会求出子问题的左边最大子段和为1

1
2
//求左边的最大子段和
leftSum=divideAndConquer(arr,left,middle);

接着右边也是一样，求出最大子段和为2
然后就是比较这个子问题的左、右、横跨左右三个子段和哪个大了，左右最大值都计算出来了，就差横跨左右的子段了。 横跨左右的子段有个特点，就是这个子段一定包含左右两边接壤的地方（中间middle这里）,所以左边让其从他的最右边开始计算最大子段（一定包含最有边的元素）， 右边让其从最左边开始计算最大子段（一定包含最左边的元素，这样才能让计算出来的结果是连续的子段），左右两边都是最大的，那最后让这两者相加就是横跨左右的子段和的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
s1=0;lefts=0;
for (int i=middle;i>=left;i--){
    lefts+=arr[i];
    if (lefts>s1){
        s1=lefts;
    }
}
s2=0;rights=0;
for (int i=middle+1;i<=right;i++){
    rights+=arr[i];
    if (rights>s2){
        s2=rights;
    }
}
midSum=s1+s2;

完整代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public int divideAndConquer(int arr[],int left,int right){
    int sum =0,midSum=0,leftSum=0,rightSum=0;
    int middle=0;
    int s1,s2,lefts,rights;
    if (left==right){
        sum = arr[left];
    }else {
        middle = (left + right)/2;
        //求左边的最大子段和
        leftSum=divideAndConquer(arr,left,middle);
        //求右边的最大子段和
        rightSum=divideAndConquer(arr,middle+1,right);
        //求横跨两边的子段和
        s1=0;lefts=0;
        for (int i=middle;i>=left;i--){
            lefts+=arr[i];
            if (lefts>s1){
                s1=lefts;
            }
        }
        s2=0;rights=0;
        for (int i=middle+1;i<=right;i++){
            rights+=arr[i];
            if (rights>s2){
                s2=rights;
            }
        }
        midSum=s1+s2;
        //比较左、右、横跨两边的子段和哪个最大
        if (midSum<leftSum){
            sum=leftSum;
        }else {
            sum=midSum;
        }
        if (sum<rightSum){
            sum=rightSum;
        }
    }
    return sum;
}