北大1050题

原题链接如下：

这题的方法和2479题类似，也是利用”求最大连续字段的和“的方法

假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，如下所示(ari表示a[r][i],假设数组下标从1开始)： 

| a11......a1i......a1j......a1n | 

| a21......a2i......a2j......a2n | 

| ........................................| 

| ar1......ari......arj......arn....| 

| ........................................| 

| ak1......aki......akj......akn..| 

| ........................................| 

| an1......ani......anj......ann | 

那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下： (ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn) 由此我们可以看出最后所求的就是此一维数组的最大子段和问题，到此我们已经将问题转化为上面的已经解决了的问题了。

解题如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXNUM 120

int    get_max_value( int *data, int n );

int    data[MAXNUM][MAXNUM];

int    main()
{
    int    N = 0;
    int    i, j;
    scanf( "%d", &N );   //N表示N×N的数组

    //get input data
    get_data( N );

    //get the result
    op_data( N );

    return 0;
}

int    get_data( N )
{
    int    i, j;
    for( i=0; i<N; i++ )
    {
        for( j=0; j<N; j++ )
        {
            scanf( "%d", &data[i][j] );
        }
    }

    return 0;
}

//按照上面的方法求最大和子矩阵
int    op_data( int N )
{
    int    tmp[MAXNUM];
    int i, j, k, l, max, value ;

    max = data[0][0];

    for( i=0; i<N; i++ )
    {
        memset( tmp, 0x00, sizeof(tmp) );
        for( j=i; j<N; j++ )
        {
    //tmp[]数组用于存储从第i行到第j行的相应列元素的和
    //例如tmp[1]=data[1][1]+[data[2][1]+data[3][1]+......
            for( k=0; k<N; k++ )
            {
                tmp[k] += data[j][k];
            }

            value = get_max_value( tmp, N );

            if( value > max )
            {
                max = value;
            }
        }
    }

    printf( "%d\n",  max );

    return 0;
}

int    get_max_value( int *data, int n )
{
    int    i;
    int    value, max;
    value = max = data[0];

    for( i=1; i<n; i++ )
    {
        if( value > 0 )
        {
            value += data[i];
        }
        else
        {
            value = data[i];
        }

        if( value > max )
        {
            max = value;
        }
    }

    return max;
}