首页 > ACM题库 > UVA > UVa-108-Maximum Sum
2014
02-15

UVa-108-Maximum Sum

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

Sample Output

15

Analysis

多维(含二维)的最大子集问题是NP问题,只能用暴力搜索解决。在搜索的过程中,如果不注意保留以前的结果,将会使复杂度大大增加。我的算法是由行开始,顺序如下:

(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还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示