学步园

        可以归结为一维数组最大子序列和的问题，关键就是要利用一维数组最大子序列和的O（n）解法。

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

int a[100][100];
int col_sum[100][100][100];
int N;

int to_max(int start_row,int end_row){//一维数组的最大子序列和
	int max=-127*100*100;
	int sum=0;
	int j;
	for(j=0;j<N;j++){
		sum+=col_sum[j][start_row][end_row];
		if(sum>max){
			max=sum;
		}
		if(sum<0){
			sum=0;
		}
	}
	return max;
}

int main(void){
	scanf("%d",&N);
	
	int i;
	int j;
	int k;
	
	for(i=0;i<N;i++){
		for(j=0;j<N;j++){
			scanf("%d",&a[i][j]);
		}
	}
	
	for(j=0;j<N;j++){
		for(i=0;i<N;i++){
			for(k=i;k<N;k++){
				if(k==i){
					col_sum[j][i][i]=a[i][j];
				}else{
					col_sum[j][i][k]=col_sum[j][i][k-1]+a[k][j];
				}
			}
		}
	}
	
	int max=-127*100*100;
	int sum=0;
	for(i=0;i<N;i++){
		for(k=i;k<N;k++){
			sum=to_max(i,k);
			if(sum>max){
				max=sum;
			}
		}
	}
	printf("%d\n",max);
	
	return 0;
}