2014
02-15

# UVa-108-Maximum Sum

## Background

A problem that is simple to solve in one dimension is often much more difficult to solve in more than one dimension. Consider satisfying a boolean expression in conjunctive normal form in which each conjunct consists of exactly 3 disjuncts. This problem (3-SAT) is NP-complete. The problem 2-SAT is solved quite efficiently, however. In contrast, some problems belong to the same complexity class regardless of the dimensionality of the problem.

## The Problem

Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. 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. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array. 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-hand corner:

 9 2 -4 1 -1 8

and has the sum of 15.

## Input and Output

The input consists of an N × 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 N2 integers separated by white-space (newlines and spaces). These N2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on 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].

The output is the sum of the maximal sub-rectangle.

## Sample Input

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

15

## Analysis

(r1), (r1, r2), …, (r1, r2, …, rn),

(r2), (r2, r3), …, (r2, r3, …, rn),

….

(rn-1), (rn-1, rn),

(rn)

## Solution

#include <iostream>
#include <stdlib.h>
using namespace std;
int main(void) {
int aMat[100][100], int aColSum[100], nDem = 100, nMaxSum = -128, nTemp;
cin >> nDem;
for (int i = 0; i < nDem; ++i) {
for (int j = 0; j < nDem; ++j) {
cin >> nTemp;
aMat[i][j] = nTemp;
}
}
for (int nRowBeg = 0; nRowBeg < nDem; ++nRowBeg) {
memset(aColSum, 0, sizeof(aColSum));
for (int nRowEnd = nRowBeg; nRowEnd < nDem; ++nRowEnd) {
int *pCol = (int*)(aMat[nRowEnd]);
for (int nCol = 0; nCol < nDem; aColSum[nCol] += pCol[nCol++]);
for (int nColBeg = 0; nColBeg < nDem; ++nColBeg) {
int nSum = 0;
for (int nColEnd = nColBeg; nColEnd < nDem; ++nColEnd) {
nSum += aColSum[nColEnd];
nMaxSum = nSum > nMaxSum ? nSum : nMaxSum;
}
}
}
}
cout << nMaxSum << endl;
return 0;
}

1. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示