UVA 108 Maximum Sum 最大连续子矩阵和

题意：给出n*n的矩阵，求出里面子矩阵的和的最大值。

这题是最大连续子序列的应用，序列是一维的，矩阵是二维的，所以我们可以把矩阵转换为一维的来算。

也就是枚举矩阵的连续几行的合并，这样就转换为一维的了，再用最大子序列的算法去求，更新最大值就可以了。

代码：

 /* *   Author:        illuz <iilluzen[at]gmail.com> *   Blog:          http://blog.csdn.net/hcbbt *   File:          uva108.cpp *   Lauguage:      C/C++ *   Create Date:   2013-09-05 15:55:37 *   Descripton:    UVA 108 Maximum Sum, dp  */#include <cstdio>#include <algorithm>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)#define repf(i, s, n) for (int i = (s); i < (n); i++)const int MAXN = 110; int m[MAXN][MAXN], s[MAXN][MAXN], a[MAXN], n;void maxSeq(int* a, int len, int &res) {res = a[0];int sum = 0;for (int i = 0; i < len; i++) {if (sum < 0)sum = a[i];else sum += a[i];if (res < sum)   res = sum;}}int main() {scanf("%d", &n);repf(i, 1, n) repf(j, 1, n) {scanf("%d", &m[i][j]);s[i][j] = s[i - 1][j] + m[i][j];}int ans = -0xfffffff, res;repf(i, 0, n - 1) repf(j, i + 1, n) {repf(k, 1, n) a[k] = s[j][k]- s[i][k];maxSeq(a + 1, n, res);ans = max(ans, res);}printf("%d\n", ans);return 0;}