CloudLander's Blog
0%

子矩阵的最大累加和问题

发表于 分类于

子矩阵的最大累加和问题
给定一个矩阵matrix，其中的值有正有负有0，返回子矩阵的最大累加和
例如，矩阵matrix为：
-90 48 78
64 -40 64
-81 -7 66
其中，最大累加和的子矩阵为：
48 78
-40 64
-7 66
所以返回累加和209

例如，matrix为：
-1 -1 -1
1 2 2
-1 -1 -1
其中最大累加和的子矩阵为
2 2
所以返回累加和为4

假设一个2行4列的矩阵如下：
-2 3 -5 7
1 4 -1 -3

可以先把两行元素累加，然后得到累加数组[-1,7,-6,4],接下来求这个累加数组的最大累加和，结果是7.也就说，必须含有2行元素的子矩阵的最大和为7，且这个子矩阵是
3
4
也就是说，如果一个矩阵共有k行且限定必须有k行元素的情况下，我们只要把矩阵中每一列的k个元素累加生成一个累加数组，然后求出这个数组的最大累加和，这个最大累加和就是必须含有k行元素的子矩阵中的最大累加和

利用题目的第一个例子来讲述：
首先考虑只有一行的矩阵[-90.48,78],因为只有一行，所以累加数组arr就是[-90.48.78]这个数组的最大累加和为126

接下来考虑含两行的矩阵
-90 48 78
64 -40 64
这个矩阵的累加数组就是上一步的累加数组[-90.48,78]的基础上，依次在每个位置上加上矩阵最新一行[64,-40,64]的结果，即[-26,8,142]，这个数组的最大累加和为150.

接下来考虑含有3行的矩阵：
-90 48 78
64 -40 64
-81 -7 66
这个矩阵的累加数组就是上一步累加数组[-26,8,142]的基础上，依次在每个位置上加上矩阵的最新一行[-81 -7 66]的结果，即[-107,1,208]，这个数组的最大累加和为209。此时，必须从矩阵第一行元素开始，并往下的所有子矩阵都已查找完毕，接下来从矩阵的第二行开始，继续这样的过程。。。

整个过程中最关键的地方有两处：

  • 用求累加数组的最大累加和的方式得到每一步的最大子矩阵的累加和
  • 每一步的累加数组可以利用前一步求出的累加数组很方便的得到
    由于求一个数组的最大子数组累加和时间复杂度为O(N),所以如果矩阵大小为N×N，则全部过程的时间复杂度为O(N^3)
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

public int maxSum(int[][] m){
    if(m==null || m.length==0 || m[0].length==0)
        return 0;
    int col = m[0].length;
    int[] sumArr = new int[col];
    int res = Integer.MIN_VALUE;
    for(int i=0;i<m.length;i++){
        Arrays.fill(sumArr, 0);
        for(int j=i;j<m.length;j++){
            for(int k=0;k<col;k++){
                sumArr[k] += m[j][k];
            }
            res = Math.max(res, maxSum(sumArr));
        }
    }
    return res;
}

//求子数组累加最大和
public int maxSum(int[] arr){
    if(arr==null || arr.length==0)
        return 0;
    int sum = arr[0];
    int res = sum;
    for(int i=1;i<arr.length;i++){
        if(arr[i]+sum>arr[i]){
            sum += arr[i];
        }else
            sum = arr[i];
        res = Math.max(sum, res);
    }
    return res;
}