【动态规划】最大子矩阵

问题：求一个n*m的矩阵中的最大子矩阵。

思路：

考虑只有一行的情况，在1*m的矩阵中，最大子矩阵可以很容易求出。 sum[j]=max(sum[j-1]+num[j], num[j])sum[j] 指的是从0开始到j的最大子段和。

考虑两行的情况，最大子矩阵可能只有1行，也可能有2行。2行的最大子矩阵可以通过上下相加合并成一行，转换成最大子段和来求。

考虑三行的情况，最大子矩阵可能有1’、2、3行。3行的最大子矩阵可以将每一列上下相加合并成一行，转换成最大子段和来求。

……

考虑n行的情况，最大子矩阵可能是1、2、……n行，每一种情况下，我们都通过把它所对应的矩阵部分上下相加才求最大子段和，最终求得最大子矩阵。

代码如下：

#include <iostream>#include <algorithm>#include <vector>#include <stdio.h>#include <cstring>using namespace std;int num[51][51];int dp[51];//求出最大子段和int getMaxArray(int N) {    int max = dp[0], tmp = 0;    for (int i = 0; i < N; ++i) {        tmp>0?tmp += dp[i]:tmp = dp[i];        max = max > tmp ? max : tmp;    }    return max;}int main(){        int n,m,i,j,k,temp,Max,a,b;        cin>>n>>m;        for(i=0;i<n;i++)                for(j=0;j<m;j++)                      cin>>num[i][j];        Max=num[0][0];        for(i=0;i<n;i++)        {                //考虑最优子矩阵从1行到n行的情况                memset(dp,0,sizeof(dp));                for(j=i;j<n;j++)                {                      //迭代求出从第i行开始，子矩阵由1行到j行的情况                      for(k=0;k<m;k++)dp[k]+=num[j][k];                      temp = getMaxArray(m);                      Max=Max> temp ? Max : temp;                }        }        PRintf("%d/n", Max);}