/*
最大子矩阵
*/
#include
<
iostream
>
using
namespace
std;
int
N;
int
s[
101
][
101
];
int
Max;
int
main()
{
cin
>>
N;
for
(
int
i
=
1
;i
<=
N;
++
i)
s[i][
0
]
=
0
;
for
(
int
i
=
1
;i
<=
N;
++
i)
for
(
int
j
=
1
;j
<=
N;
++
j){
cin
>>
s[i][j];
s[i][j]
+=
s[i][j
-
1
];
}
Max
=-
0xFFFFFFF
;
int
m;
for
(
int
k
=
1
;k
<=
N;
++
k)
for
(
int
i
=
k;i
<=
N;
++
i){
m
=
s[
1
][i]
-
s[
1
][k
-
1
];
if
(m
>
Max) Max
=
m;
for
(
int
j
=
2
;j
<=
N;
++
j){
if
(m
<
0
) m
=
s[j][i]
-
s[j][k
-
1
];
else
m
+=
s[j][i]
-
s[j][k
-
1
];
if
(m
>
Max) Max
=
m;
}
}
cout
<<
Max
<<
endl;
return
0
;
}
posted on 2009-05-30 20:26
xfstart07 阅读(157)
评论(0) 编辑 收藏 引用 所属分类:
代码库