Juan Céspedes - Programas 

Problemas resueltos del Juez Online de la UVa 

Maximum Sum

108.c

/* Maximum Sum */
/* Dynamic Programming */
#include <stdio.h>
#include <string.h>

int dim;
char array[100][100];

int maximum_sum(int * a)
{
	register int i;
	register int max;
	int sums[101];

	max=sums[0]=a[0];
	for(i=1; i<dim; i++) {
		if (sums[i-1]>0) {
			sums[i] = sums[i-1]+a[i];
		} else {
			sums[i] = a[i];
		}
		if (sums[i]>max) {
			max=sums[i];
		}
	}
	return max;
}

void
calc(void)
{
	int i,j;
	int a;
	int max=array[0][0];
	int tmp[100];
	int sum;

	for(i=0; i<dim; i++) {
		memset(tmp,0,dim*sizeof(int));
		for(j=i; j<dim; j++) {
			for(a=0; a<dim; a++) {
				tmp[a] += array[j][a];
			}
			sum = maximum_sum(tmp);
			if (sum > max) {
				max=sum;
			}
		}
	}
	printf("%d\n", max);
}

int
main(void)
{
	int i,j;

	scanf("%d", &dim);
	for(i=0; i<dim; i++) {
		for(j=0; j<dim; j++) {
			int a;
			scanf("%d",&a);
			array[i][j]=a;
		}
	}
	calc();
	exit(0);
}