poj 1050 求和问题

题意：给定一个n*n的矩阵，求一个子矩阵，使得该矩阵的元素之和最大。

思路：经典的DP。由一维到二维。

      1.必须先了解一维的情况，对于一维的数组而言，则转化为用DP求最大连续子序列，DP的状态方程为：sum[i] = max（sum[i-1] + num[i], 0)。

      例如： num[]： -5， 7, -2, -6， 5, -1， 4

             sum[]：  0， 7， 5， 0， 5,  4,  8

      2.对于二维的情况，则可转化为一维。将子矩阵的所有相同列的元素加在一起，问题就解决了。

      例如： 若子矩阵为: -1, -2, -3,  5,  4

                          2, -5,  4,  7,  6

                          5,  5, -6, -2, -7

              则now[]为： 6,  3, -5, 10, -3

代码：

#include<iostream>
using namespace std;
const int Max = 105;

int max(int a, int b)
{
    return a > b ? a : b;
}

int main()
{
    int n, i, j, k, row, col, sum, ans;
    int num[Max][Max], now[Max];
    cin >> n;
    row = col = n;
    for(i = 0; i < row; i ++)
        for(j = 0; j < col; j ++)
            cin >> num[i][j];
		ans = sum = 0;
		for(i = 0; i < row; i ++)
		{
			memset(now, 0, sizeof(now));
			for(j = i; j < row; j ++)    //  求第i行到第j行的子矩阵。
				for(k = 0, sum = 0; k < col; k ++)
				{ 
					now[k] += num[j][k];
					sum = max(sum + now[k], 0);
					if(sum > ans) 
						ans = sum;
	
				}
		}
		cout << ans << endl;
		return 0;
}