To the Max
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*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.
Input
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 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].
Output
Output 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
Source
题目类型：线性dp扩展
算法分析： 使用变量i和j(i <= j)枚举所有的行下标，然后将同列的数压缩成一个数。使得二维的矩阵变成了一个一维的数组，然后直接求解最大连续子段和即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 100 + 6; short ans[maxn][maxn], sum[maxn][maxn], dp[maxn][maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int n; while (cin >> n) { for (int i = 1;i <= n; i++) for (int j = 1; j <= n; j++) cin >> ans[i][j]; memset (sum, 0, sizeof (sum)); memset (dp, 0, sizeof (dp)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum[i][j] = sum[i-1][j] + ans[i][j]; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) for (int k = 1; k <= n; k++) { int temp = sum[j][k] - sum[i-1][k]; dp[i][j][k] = max (dp[i][j][k-1] + temp, temp); } short maxval = -INF; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) maxval = max (maxval, dp[i][j][k]); cout << maxval << endl; } return 0; } |
不使用dp数组来存储中间结果，直接边算边更新最大值，可以优化空间复杂度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> #define lson rt << 1, l, m #define rson rt << 1 | 1, m + 1, r using namespace std; const int INF = 0x7FFFFFFF; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int MOD = 7; const int maxn = 100 + 6; int ans[maxn][maxn], sum[maxn][maxn]; int main() { // ifstream cin ("aaa.txt"); int n; while (cin >> n) { for (int i = 1;i <= n; i++) for (int j = 1; j <= n; j++) cin >> ans[i][j]; memset (sum, 0, sizeof (sum)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum[i][j] = sum[i-1][j] + ans[i][j]; int maxval = -INF, tempsum, tempval; for (int i = 1; i <= n; i++) for (int j = i; j <= n; j++) { tempsum = -INF, tempval = 0; for (int k = 1; k <= n; k++) { int temp = sum[j][k] - sum[i-1][k]; if (tempval > 0) tempval += temp; else tempval = temp; tempsum = max (tempsum, tempval); } maxval = max (maxval, tempsum); } cout << maxval << endl; } return 0; } |
- « 上一篇：poj1047
- poj1060：下一篇 »