1121: 最大子矩阵

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:86 通过:26

题目描述

给定一个含有正负数的二维数组,找出有最大和的子矩阵。矩阵的和指矩阵中所有元素的和。
一个子矩阵是任意在总矩阵中大小为1x1或更大的邻近子数组

输入格式

输入第一行为正整数n,表示n*n的矩阵(1<=n<=100)
接下来n行,每行输入n个整数。数字大小在[-127,127]以内。

输出格式

输出一个整数表示最大子矩阵的和

输入样例 复制

4
0 -2 -7 0 
9 2 -6 2
-4 1 -4 1 
-1 8 0 -2

输出样例 复制

15