给定一个n*n(0<n<=100)的矩阵,请找到此矩阵的一个子矩阵,并且此子矩阵的各个元素的和最大,输出这个最大的值。
Example:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其中左上角的子矩阵:
9 2
-4 1
-1 8
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。
\#include "stdafx.h"\
\
int g\_Mat[101][101] =\
{\
{ 0, -2, -7, 0 },\
{ 9, 2, -6, 2 },\
{ -4, 1, -4, 1 },\
{ -1, 8, 0, -2 },\
};\
\
int GetSumOfMaxSubMatrix(){\
int eachColSum[4]; // 每列之和.\
\
int maxSum = std::numeric\_limits\<int\>::min();\
\
for( int rowStart = 0; rowStart \< 4; rowStart++ )\
{\
// 初始情况下,清零.\
memset( eachColSum, 0, sizeof(eachColSum) );\
for( int rowEnd = rowStart; rowEnd \< 4; rowEnd++ )\
{\
// 当前测试矩阵为[ [rowStart][0],[rowEnd][4] ].\
for( int col = 0; col \< 4; col++ )\
eachColSum[col] += g\_Mat[rowEnd][col];\
\
// 相当于一维的情况.\
int curSum = eachColSum[0];\
for( int col = 1; col \< 4; col++ ){\
if( curSum \< 0 )\
curSum = eachColSum[col];\
else\
curSum += eachColSum[col];\
\
if( maxSum \< curSum ) maxSum = curSum;\
}\
}\
}\
\
return maxSum;\
}\
int main(){\
cout \<\< GetSumOfMaxSubMatrix() \<\< endl;\
}\
/\*\
15\
\*/
Reference: 编程之美——2.15 子数组之和的最大值(二维).