HDU 1081 To The Max

题目描述

题意：给定N * N的矩阵，每个位置都有一个[-128, 127]的数字，求一个子矩阵，满足子矩阵中数字和最大，并输出这个最大值。

样例

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

输出：

15

算法：

这题可以用DP做，也可以用贪心思想。这里使用贪心作为解。

首先我们要知道，对于一维数组而言，如何求出最大它的子段最大和？

我们只需要O(n)地扫描一遍该数列，不断把新的值加入子段，当子段和小于0时，要把当前字段和清空(再加入数字，明显与0相加更优)，不断在扫描中更新最大值即可。

那么，对于二维矩阵，如何求出最大子矩阵？

我们可以枚举每个i ~ j行，把该i ~ j行的数字和看作一个"点"，这样就可以用一维的方法求出在行数限定为i~j时，求出的最大矩阵和，由于枚举了所有i ~ j的情况，答案不会更优，因此求的的答案为最优解。

复杂度计算：枚举每个i ~ j行的状态，在每个状态下，需要计算每一列中i ~ j行的和，矩阵是N * N的，因此复杂度为O(n³)，n最大为100,共需要计算10⁶次，可以接受。

唯一的坑点就是有多组输入，而题目没有说明。

代码如下：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 105;

int n; // n*n矩阵
int w[N][N];
int t[N], ans; // t存储第i~j行的sum，ans存储最优解

int main () {
    #ifdef LOCAL
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    
    while (cin >> n) {
        ans = 0; // 新组，要更新ans为0,否则可能引入上一组max
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cin >> w[i][j];

        // 把i~j行看成一个点，往右推进，形成一个一维最大sum的子序列
        for (int i = 1; i <= n; i++) {
            memset(t, 0, sizeof t);
            for (int j = i; j <= n; j++) { // 枚举i~j行的点值
                for (int k = 1; k <= n; k++)  t[k] += w[j][k];

                for (int k = 1, maxi = 0; k <= n; k++) {
                    maxi += t[k];
                    ans = max(ans, maxi);
                    if (maxi < 0) maxi = 0;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}