一个二维的最大连续子串问题,地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1050

#include < stdio.h >


int table[105][105];
int dp[105][105][105];


int main ()
{
    
    
int n,i,j,z;
    
int b,sum,result;
    
    
while ( scanf ( "%d"&n ) != EOF )
    
{
        
for ( i=0; i<n; i++ )
        
{
            
for ( j=0; j<n; j++ )
            
{
                scanf ( 
"%d"&table[i][j] );
            }

        }

        
        
for( i=0; i<n; i++ )
        
{
            
for ( j=i; j<n; j++ )
            
{
                
for ( z=0; z<n; z++ )
                
{
                    
if ( i != j )
                    
{
                        dp[i][j][z] 
= dp[i][j-1][z] + table[j][z];
                    }

                    
else
                    
{
                        dp[i][j][z] 
= table[j][z];
                    }

                }

            }

        }

        
        result 
= dp[0][0][0];
        
        
for ( i=0; i<n; i++ )
        
{
            
for ( j=0; j<n; j++ )
            
{
                sum 
= dp[i][j][0];
                b 
= 0;
                
for ( z=0; z<n; z++ )//dp 就一维的
                {
                    
if ( b > 0 )
                    
{
                        b 
+= dp[i][j][z];
                    }

                    
else 
                    
{
                        b 
= dp[i][j][z];
                    }

                    
                    
if( b > sum )
                    
{
                        sum  
= b;
                    }

                }

                
if ( sum > result )
                
{
                    result 
= sum;
                }

            }

        }

        printf ( 
"%d\n", result );
    }

    
return 0;
}