Dynamic Programming Example:Maximum Sum Submatrix in Matrix


(anaiw) #1

作者:刘帝伟
原文链接:Dynamic Programming Example:Maximum Sum Submatrix in Matrix
新浪微博:@拾毅者

BitTiger坚决尊重拥护原创版权,本文转载已经经过作者授权,如需转载请联系原作者。

问题描述

Find maximum sum submatrix in a given 2D matrix of integers.

输入

  • 第1组n m:表示一个数组是nn行mm列的;
  • 第2组:输入第一个nn行mm列的数组;

返回

  • 最大子矩阵和

样例:

给定一个n∗mn∗m维的二维数据,如下

4    4
0    -2    -7    0
9    2    -6    2
-4    1    -4    1
-1    8    0    -2

最后输出子矩阵和:

15

最大连续子序列和

最大子矩阵与最大连续子序列和有着千丝万缕的联系,最大连续子序列的DP动态转移方程为

![dp[i]=max(dp[i-1]+arr[i],arr[i])

](https://www.zhihu.com/equation?tex=dp[i]%3Dmax(dp[i-1]%2Barr[i]%2Carr[i]) )

其中dp[i]dp[i]表示从左到右到第ii个元素时的最大子序列和, arrarr 是子序列,这里可以使用一维数组表示。代码如下:

int maxSubArray(vector<int> arr){
    int n = arr.size();
    vector<int> dp(n);
    int maxVal = INT_MIN;
    for(int i = 0; i < n; ++i){
        dp[i] = i == 0 ? arr[i] : max(arr[i], dp[i - 1] + arr[i]);
        maxVal = maxVal > dp[i] ? maxVal : dp[i];
    }
    return maxVal;
}

通过设置一个最大和变量maxVal,每次获取dp[i]dp[i]时就将两者比较一下,并将大的赋值给maxVal即可。

最大子矩阵和

Step1: 构造行和矩阵

首先开辟一个临时矩阵sumMatrix,第ii行各列的元素表示的是原始矩阵matrixmatrix第00行到第ii行各列的元素之和,使用公式表示就是:

sumMatrix[i][j]=\sum_{k=0}^{i} matrix[k][j]

可以将原始矩阵转为行和矩阵:

![](data:image/svg+xml;utf8,)

Step2:寻找状态转移矩阵

变量说明:

  • matrix: 原始矩阵
  • sumMatrix: 行和矩阵

解释一

分析下,如果最终得到的是一维子数组,那么有两种情况,第一种是行子数组,第二种是列子数组,如果是行子数组,则相当于在原数组matrix上对每行执行一次最大连续子序列和方法并取最大的值即可,如果切换到行和矩阵上,则原始数据matrix的第ii行等价于行和矩阵sumMatrix的第ii行减去i−1i−1行的值,即sumMatrix[i][j]−sumMatrix[i−1][j]sumMatrix[i][j]−sumMatrix[i−1][j];同理,如果是列子数组,假设是第ii行到第jj行的列子数组,则等价到行和数组上,就是第jj行每一列的值减去第ii行每一列的值,然后求解此时最大的一列即可。那么,如果是多行多列的子数组呢?

对于这种情况,可以设置一个变量kk,用以调整子矩阵的行数,当kk等于0的时候,表示的是一维数组,也就是上面讨论的一维行子矩阵的情况;当kk等于11的时候,则表示子矩阵的行数为22,那么通过什么来获取这个子矩阵呢?我们可以根据行和矩阵,以间隔为11进行相减获取子矩阵的列和并将其转为一维数组,即sumMatrix[i][j]−sumMatrix[i−1−1][j]sumMatrix[i][j]−sumMatrix[i−1−1][j];同理,当kk等于2,3,⋯2,3,⋯的时候,子矩阵的列和就为sumMatrix[i][j]−sumMatrix[i−1−k][j]sumMatrix[i][j]−sumMatrix[i−1−k][j],然后求解此时的一维数组的最大子序列和,需要注意的是,当i==ki==k时,由于是k+1k+1行相加,因此首行就是sumMatrix[i][j]sumMatrix[i][j]。 因此可以得到下列递推式式子:

temp[j] = k == 0 ? matrix[i][j] : i == k ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[i - k - 1][j]

解释二

同样设置一个变量kk,并且此时的kk同样代表子矩阵的行数,但规则不一样。当k=0k=0时,我们根据行号ii来确定子矩阵的行数,如果是第ii行,则表示子矩阵的行数也是ii取值为前ii行,也就是行和矩阵sumMatrix[i][j]sumMatrix[i][j];当k=1k=1时,则当行号为ii时,我们取(k, i]行之间的元素,即sumMatrix[i][j]−sumMatrix[i−k][j]sumMatrix[i][j]−sumMatrix[i−k][j]。因此可以得到下列状态转移方程:

temp[j] = k == 0 ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[i - k][j]

解释三

同样设置一个变量kk,此kk用以表示子矩阵的首行,由于子矩阵肯定是连续的行,因此,当k=0k=0时,根据行号ii依次得到子矩阵的行和[0,i][0,i];当k=1k=1时,表示子矩阵的首行为11,根据ii依次得到[k,i][k,i]行的元素;由此可以得出状态转移矩阵为:

temp[j] = k == 0 ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[k-1][j];

当得到这个递推式子之后,每次得到新的子矩阵列和,然后根据新的一维数组求解最大连续子序列。

上面给出了三种解释,因此可以根据之前的推导编写出下列代码,源代码如下:

#include<iostream>
#include<vector>
using namespace std;
int maxSubArray(vector<int> arr);
int maximumSubMatrix(vector<vector<int> > matrix);
int main(){
    int n, m;
    while(cin>>n>>m){
        vector<vector<int> > matrix;
        for(int i = 0; i < n; i++){
            vector<int> temp;
            for(int j = 0; j < m; ++j){
                int value;
                cin>>value;
                temp.push_back(value);
            }
            matrix.push_back(temp);
        }
        cout<<maximumSubMatrix(matrix)<<endl;
    }
    return 0;
}

int maxSubArray(vector<int> arr){
    int n = arr.size();
    vector<int> dp(n);
    int maxVal = INT_MIN;
    for(int i = 0; i < n; ++i){
        dp[i] = i == 0 ? arr[i] : max(arr[i], dp[i - 1] + arr[i]);
        maxVal = maxVal > dp[i] ? maxVal : dp[i];
    }
    return maxVal;
}

int maximumSubMatrix(vector<vector<int> > matrix){
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int> > sumMatrix(n, vector<int>(m)), dp(n, vector<int>(m));
    int i, j, k;
    for(i = 0; i < n; ++i){
        for(j = 0; j < m; ++j){
           sumMatrix[i][j] =  i == 0 ? matrix[i][j] : sumMatrix[i-1][j] + matrix[i][j];
        }
    }
    int maxVal = INT_MIN;
    vector<int> temp(m);
    for(k = 0; k < n; ++k){
        for(i = k; i < n; ++i){
            for(j = 0; j < m; ++j){
                //temp[j] = k == 0 ? matrix[i][j] : i == k ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[i - k - 1][j];
                temp[j] = k == 0 ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[i - k][j];
                //temp[j] = k == 0 ? sumMatrix[i][j] : sumMatrix[i][j] - sumMatrix[k - 1][j];
            }
            int arrVal = maxSubArray(temp);
            maxVal = max(maxVal, arrVal);
        }
    }
    return maxVal;
}

关于DP,有个博客讲解的非常详实,感兴趣的可以看看,地址:演算法笔记

References

—————————————————————————————————————————

BitTiger算法第二期上线啦!报名免费试听→点击这里

NoSQL作为面试中高频题目,掌握好了吗?课程详情→点击这里

更多精彩,尽在硅谷高端线上教育社区BitTiger:请猛戳我

公众号:论码农的自我修养

微博:@太阁BitTiger

今日头条:太阁BitTiger