浙大在线评测 1074 To the Max

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

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 right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].

Input:

4

0 -2 -7 0 9 2 -6 2

-4 1 -4 1 -1

8 0 -2

Output:

15

Solution:

// 声明:本代码仅供学习之用,请不要作为个人的成绩提交。

// http://blog.csdn.net/mskia

// email: bitrain@hotmail.com

#include <iostream.h>

const int N=100;

int array[N][N];

int main( void ) {

int n;

cin >> n;

for( int i = 0 ; i < n ; ++i ) {

for( int j = 0 ; j < n ; ++j ) {

cin >> array[ i ][ j ] ;

}

}

int sum = maxSum2 ( n );

cout << sum << endl;

return 0;

}

int maxSum( int n , int *p ) {

int sum = 0 , b = 0;

for( int i = 0 ; i < n ; ++i ) {

if ( b > 0 ) {

b += * ( p + i ) ;

} else {

b = * ( p + i ) ;

}

if ( b > sum ) {

sum = b;

}

}

return sum;

}

int maxSum2( int n ) {

int sum = 0 ;

int *b = new int [ n ];

for( int i = 0 ; i < n ; ++i ) {

for( int k = 0 ; k < n ; ++k ) {

*( b + k ) = array [ i ][ k ] ;

}

for( int j = i + 1 ; j < n ; ++j ) {

for( int k = 0 ; k < n ; ++k ) {

*( b + k ) += array [ j ][ k ] ;

}

}

int max = maxSum( n , b );

if( max > sum ) {

sum = max ;

}

}

return sum;

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航