题目名称 2219. [POJ 1050]最大子矩阵和
输入输出 submatrixsum.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravatarsyzhaoss 于2016-04-10加入
开放分组 全部用户
提交状态
分类标签
贪心
分享题解
通过:2, 提交:2, 通过率:100%
GravatardarkMoon 100 0.055 s 2.36 MiB C++
Gravatarlihaoze 100 0.338 s 3.47 MiB C++
关于 最大子矩阵和 的近10条评论(全部评论)

2219. [POJ 1050]最大子矩阵和

★★   输入文件:submatrixsum.in   输出文件:submatrixsum.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】

给定一个包含整数的二维矩阵,子矩阵是位于整个阵列内的任何大小为 1×1 或更大的连续子阵列。

矩阵的总和是该矩阵中所有元素的总和。

在这个问题中,具有最大和的子矩阵被称为最大子矩阵。

【输入格式】

输入中将包含一个 N×N 的整数数组。

第一行只输入一个整数 N,表示矩阵的大小。

从第二行开始,输入由空格和换行符隔开的 $N^2$ 个整数,它们即为矩阵中的 $N^2$ 个元素,输入顺序从矩阵的第一行开始向下逐行输入,同一行数据从左向右逐个输入。

【输出格式】

输出一个整数,代表最大子矩阵的总和。

【样例输入】

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

【样例输出】

15

【样例解释】

最大子矩阵为:

9 2 
-4 1 
-1 8

它拥有最大和 15。

【数据规模与约定】

$1\leq N\leq 100$。

矩阵中的数字会保持在 [-127,127] 的范围内。