UC知道C C++ java
来源：百度知道 编辑：UC知道 时间：2024/06/28 13:24:07
to the Max
Problem
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to r
Problem
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to r
我的理解是，1个2维数组有正数，负数。1个sub-rectangle （内数组？）是这个2维数组中1x1或者更大的数组。在这些内数组中有1个最大内数组是所有元素加起来结果最大的那个数组。
例如
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大内数组是左下的
9 2
-4 1
-1 8
要求，先输入1个数字n指定这个数组是NxN的数组，
然后输入每个数字，最后输出最大内数组的求和值
还真够懒的。。。。
说个思路
假设传进来是n维矩阵k[n][n]
定义四个变量 w,x,y,z 初始为0
嵌套循环w,x,y,z
for(w=0,w<n,w++)
{
for(x=0,x<n,x++)
{
for(y=0,y<n,y++)
{
for(z=0,z<n,z++)
{
这里面的k[w][x]到k[y][z],肯定能包括所有情况，计算k[w][x]到k[y][z]的sum值，存入hashmap或者数组，然后取hashmap中最大值即可。
如果想知道坐标，把w,x,y,z也记录下来。
这个算法效率不高，因为有重复(1,2)->(3,4)的值与(3,4)->(1,2)的值相同
with C C++ to edit code is not a difficult job,
different one is your language .i can't help you.
even so invalid words in here. lol...
我记得是poj上的题。