問題：求一個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);}