学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1081

DP,最大矩阵和，首先将横坐标的数值，分别求和存储在二维数组中，然后使用三个for循环，第一二层分别表示第I 横层 ，和第j 横层，然后做差，就求出了纵坐标的和，当sum〉0就由k 向右累加；

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std ;

int dp[ 150 ][ 150 ] ;

int main()
{
	int n ;
	int i , j , k , t , maxn ;
	while( ~scanf( "%d" , &n ) )
	{
		memset( dp , 0 , sizeof( dp ) );
		for( i = 0 ; i < n ; ++i )
			for( j = 0 ; j < n ; ++j )
			{
				scanf( "%d" , &t ) ;
				dp[ i ][ j ] = dp[ i - 1 ][ j ] + t ;
			}
			maxn = -1 ;
			for( i = 0 ; i < n ; ++i )
				for( j = i ; j < n ; ++j )
				{
					int sum = 0 ;
					for( k = 0 ; k < n ; ++k )
					{
						t = dp[ j ][ k ] - dp[ i - 1 ][ k ] ; 
						sum += t ;
						if( sum < 0 )
							sum = 0 ;
						if ( sum > maxn )
							maxn = sum ;
					}
				}
				printf( "%d\n" , maxn ) ;
	}
	return 0 ;
}