xfstart07
Get busy living or get busy dying

/*
最大子矩阵
*/
#include
< iostream >
using   namespace  std;

int  N;
int  s[ 101 ][ 101 ];
int  Max;
int  main()
{
    cin
>> N;
    
for ( int  i = 1 ;i <= N; ++ i)
        s[i][
0 ] = 0 ;
    
for ( int  i = 1 ;i <= N; ++ i)
        
for ( int  j = 1 ;j <= N; ++ j){
            cin
>> s[i][j];
            s[i][j]
+= s[i][j - 1 ];
        }
    Max
=- 0xFFFFFFF ;
    
int  m;
    
for ( int  k = 1 ;k <= N; ++ k)
        
for ( int  i = k;i <= N; ++ i){
            m
= s[ 1 ][i] - s[ 1 ][k - 1 ];
            
if (m > Max) Max = m;
            
for ( int  j = 2 ;j <= N; ++ j){
                
if (m < 0 ) m = s[j][i] - s[j][k - 1 ];
                
else  m += s[j][i] - s[j][k - 1 ];
                
if (m > Max) Max = m;
            }
        }
    cout
<< Max << endl;
    
return   0 ;
}





posted on 2009-05-30 20:26 xfstart07 阅读(155) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理