uva 108 Maximum Sum

把所有 subrectangles (左上到右下角 )都算出來，以左上角為基準點和 rectangle 裡的任一點

形成的 rectangle，

再一一討論原本 rectangle 裡的所有 subrectangles，利用

算出每一個討論的 rectangle，把最大的找出來。


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

int main(void){
    int length;
    int i,j,k,m;
    int rectangle[101][101]={0},maximum,tmp;

    while(scanf("%d",&length)!=EOF){
        for(i=1;i<=length;i++){
            for(j=1;j<=length;j++){
                scanf("%d",&rectangle[i][j]);
                rectangle[i][j]+=rectangle[i-1][j]+rectangle[i][j-1]-rectangle[i-1][j-1];
            }
        }

        maximum=0;
        for(i=1;i<=length;i++){
            for(j=1;j<=length;j++){

                for(k=i;k<=length;k++){
                    for(m=j;m<=length;m++){
                        tmp=rectangle[k][m]-rectangle[i-1][m]-rectangle[k][j-1]+rectangle[i-1][j-1];
                        if(tmp>maximum) maximum=tmp;
                    }
                }

            }
        }

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

    return 0;
}