题目大意：输入N*N矩阵，输出最大子矩阵和。
解题策略：这道题为DP经典问题——最大连续区间和的拓展，
http://www.stackpop.org/html/503_2d_max_interval.html 这位大牛把我意会却无法言传的部分都说了，分析透彻，图文并茂。
PS：网上求连续区间和的方法略慢，大家可以对比着看，能快0.005s左右。
/*
UVA 108 Maximum Sum
POJ 1050 To the Max
AC by J.Dark
ON 2013/3/20
Time 0.015s
*/
#include
#include
#include
#include
using namespace std;
const int maxn = 110;
int N, martix[maxn][maxn];
inline void input(){
for(int i=0;
i> martix[i][j];
}
}
}//求最大连续子区间和，网上算法几乎一样
//自己写了一个，比较简单，较快
int max_sum(int *b){
int C_sum = 0;
int temp=0;
for(int i=0;
i C_sum)C_sum = temp;
if(temp < 0)temp = 0;
}
return C_sum;
}inline void solve(){
int b[maxn];
//memset(b, 0, sizeof(b));
int maxSum = 0;
for(int i=0;
i> N)
{
input();
solve();
}
//system("pause");
return 0;
}
【UVA 108 Maximum Sum (最大子矩阵和) POJ 1050】
