学步园

题意：给定一个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
        变为： 6,  3, -5, 10, -3

#include < iostream >
using namespace std;

int maxSubArray ( int size, int array[] )
{
	int b = array[0];
	int i,max = array[0];
	for ( i = 1; i < size; i++ )
	{
		if ( b > 0 )
			b += array[i];
		else
			b = array[i];
		if ( b > max )
			max = b;
	}
	return max;
}

int maxSubMatri ( int x, int y, int array[][101] )
{
	int set[101];
	int i,j,k,temp,max = -130;
	for ( i = 0; i < x; i++ )
	{
		for ( k = 0; k < y; k++ )
			set[k] = 0;
		for ( j = i; j < x; j++ )
		{
			for ( k = 0; k < y; k++ )
				set[k] += array[j][k];
			temp = maxSubArray(y,set);
			if ( temp > max )
				max = temp;
		}
	}
	return max;
}

int main()
{
	int n,i,j;
	int array[101][101];
	cin >> n;
	for ( i = 0; i < n; i++ )
		for ( j = 0; j < n; j++ )
			cin >> array[i][j];
	cout << maxSubMatri(n,n,array) << endl;
	return 0;
}