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: [email protected]
#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;
}
|
本类阅读TOP10