算法学习-连续最大子数组模板（JAVA实现）

本文最后更新于：January 28, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

分为连续子数组和非连续子数组，在一维的情况下可以等同于字串和子序列的最大和。

连续子数组

对于一个数A[ i ]，若是A[ i ] 的左边累计数非负，那么加上A[ i ] 能使得值不小于A[ i ]，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和。

一维

动态规划：算法时间复杂度：O(n)

对于一个数A[ i ]，若是A[ i ] 的左边累计数非负，那么加上A[ i ] 能使得值不小于A[ i ]，认为累计值对整体和是有贡献的。如果前几项累计值负数，则认为有害于总和，应丢弃。

dp[ i ]表示以a[ i ]结尾的「连续子数组的最大和」，不是整个数组的最大子数组和。

即：dp[ i ] = max{dp[ i-1 ] + a[ i ]，a[ i ] }；

初始状态：dp[0] = a[0];

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;


    public static void main(String[] args) throws Exception {

        int n = nextInt();
        int[] a = new int[maxd];
        int[] dp = new int[maxd]; //dp[i]表示以a[i]结尾的「连续子数组的最大和」
        for(int i=1;i<=n;++i) a[i] = nextInt();
        int ans = a[1]; //ans用来存储最后的答案
        dp[1]=a[1]; //初始化第一个数默认是它自己
        for(int i=1;i<=n;++i){ //如果a数组是从0开始存的，这里必须从第二个数开始，否则会存在下标为 0-1=-1 的情况.而现在这里从1或2开始都行
            dp[i]=Math.max(dp[i-1]+a[i],a[i]);
            ans=Math.max(ans,dp[i]);
        }
        System.out.println(ans);
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

测试数据：

1
2
3
4
5
6
//输入
9
-2 1 -3 4 -1 2 1 -5 4

//输出    
6

滚动数组（空间优化）

因为，dp[ i ] 只与dp[ i-1] 有关，所以可以用一个变量 midsum 来维护对于当前 dp[ i ]的dp[ i-1 ] 的值是多少，从而让空间复杂度降低到 O(1)，这类似「滚动数组」的思想。

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;

    public static void main(String[] args) throws Exception {

        int n = nextInt();
        int[] a = new int[100]; //原数组
        for(int i=1;i<=n;++i) a[i] = nextInt();
        int midsum = a[1]; //初始化
        int ans = a[1]; //默认答案为第一个数
        for(int i=1;i<=n;++i){
            midsum=Math.max(midsum+a[i],a[i]);
            ans=Math.max(ans,midsum);
        }
        System.out.println(ans);
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

二维

将二维转化为一维数组计算，然后计算一维的最大子数组问题。

方法：将每一列求一个前缀和，得到一个一维数组。

时间复杂度：O(n*n*m)

矩阵转置

看网上的一些说明，当行大于列时进行转置（因为遍历的时候是遍历的行，所以找行、列中的较小值作为行可以减少遍历次数），但感觉根本没用，因为后面求的时候行和列都用到了，时间复杂度根本没变。但是这里也写上吧。

1
2
3
4
5
6
7
8
9
public static int[][] Matreverse(int[][] a,int m,int n) { //m行n列的数组a，a数组下标从1开始
    int[][] newArr = new int[n+5][m+5]; //转化后的n行m列数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            newArr[j][i] = a[i][j];
        }
    }
    return newArr;
}

代码实现

这里没有用转置。（感觉用了没用）

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 200000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;

    //求一维数组的最大子数组
    public static int getOne(int[]a,int n){ //n为长度，a数组是下标从1开始存储的
        int[] dp = new int[maxd]; //dp[i]表示以a[i]结尾的「连续子数组的最大和」
        int ans = a[1]; //ans用来存储最后的答案
        dp[1]=a[1]; //初始化第一个数默认是它自己
        for(int i=1;i<=n;++i){ //如果a数组是从0开始存的，这里必须从第二个数开始，否则会存在下标为 0-1=-1 的情况.而现在这里从1或2开始都行
            dp[i]=Math.max(dp[i-1]+a[i],a[i]);
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {

        int n = nextInt(); //行
        int m = nextInt(); //列
        int[][] a = new int[100][100]; //原数组
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                a[i][j] = nextInt();
            }
        }
        //求每一列的前缀和，每一列中从第一行到第i行的和
        int[][] p = new int[105][105]; //p[i][j]表示j这一列的前i个数的和
        for(int i=1;i<=n;++i){
            for(int j=1;j<=m;++j){
                p[i][j]=p[i-1][j]+a[i][j];
            }
        }

        int maxans = 0;
        for(int i=1;i<=n;++i){ //第i行
            for(int j=i;j<=n;++j){ //到最后一行
                maxans=Math.max(maxans,getOne(p[i],m));
            }
        }
        System.out.println(maxans);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

测试数据：

1
2
3
4
5
6
7
//输入
2 3
1 2 3
3 -1 4

//输出
12