【大白话版】求最大和子数组的动态规划算法

Posted on |

题目：求连续子数组的最大和
要求：时间复杂度O(n)
算法思路：
基于动态规划的思想：
1、算法中维护两个最大和：全局最大和max、局部最大和sum
2、全局最大和的维护：当局部>全局时，更新全局，将其赋值为局部值
3、局部最大和的维护：若当前局部<0，则新的最大和将不包含前面累积的最大和（因为前面的累积 对于 得到最大和 起的是负作用），那么新的最大和将是下一个元素本身。若当前局部>=0，则新的最大和将包含前面累积的最大和（前面的累积起正作用），那么新的最大和将是旧最大和（即前面累积）+下一个元素
4、这里的思想就是：根据前面累积的和起正作用还是负作用，来判断是否要重新起一个新的子数组的头；而往前面的累积上加新元素应当加到何时停止，则是通过max与sum的比较来看的：如果sum大，说明新加的元素起到的是正作用，如果sum不如max大，说明新加的元素起到的是负作用。直到sum中加的一系列连续的新元素起到正作用的时候，才更新max，不然max就一直停留在之前那个最好的局部最优的值上
5、也就是说局部sum维护的是子数组的头要从哪里开始才能达到最优，而全局的max维护的是子数组的尾在哪里结束
6、另外：如果要求的不止是最大和，还要求子数组（也就是记录产生这个最大和的子数组的起止下标，那就还是基于局部和全局的思想，维护两对起止下标就可以了，只有sum>max导致max更新时，全局下标才跟着局部下标更新；局部下标则在另起新数组时更新为起止都是新元素下标，不另起时，每加一个元素就把尾端下标+1更新就可以了）

java代码实现：

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
public class MaxSumSubset {
    private int p,q;//全局起止下标
    private int m,n;//局部起止下标
    public MaxSumSubset(){
        this.p=0;
        this.q=0;
        this.m=0;
        this.n=0;
    }

    public int getP(){
        return this.p;
    }

    public int getQ(){
        return this.q;
    }

    public int getMaxSum(int[] A){
        int max = 0;//全局最大和
        int sum = 0;//局部最大和
        for(int i=0;i<A.length;i++){
            if(sum<0){
                sum = A[i];//前面累积起负作用时，用下一个元素另起一个新累积
                m = i;
                n = i;
            }else{
                sum += A[i];//前面累积起正作用时，在累积基础上加新元素
                n++;
            }
            if(max<sum){//局部大于全局时，更新全局
                max = sum;
                p = m;
                q = n;
            }
        }
        return max;
    }
}

main函数测试：

1
2
3
4
5
6
7
8
9
public class Main {

    public static void main(String[] args) {
        int[] a = {1,-2,3,5,-4,9,16,-7,5};
        MaxSumSubset mss = new MaxSumSubset();
        int max = mss.getMaxSum(a);
        System.out.println("sub set is from "+ mss.getP() +" to "+ mss.getQ() + " and max is "+ max);
    }
}