1. Erste Version: C, Evgeni Pavlidis


/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.220
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <stdio.h>
#include <limits.h>

#define MAX 20000

int routes;
int stops;

int route[MAX];

int bestStart;
int bestEnd;

int main()
{
scanf("%d\n", &routes);

int r;
for(r=1; r <= routes; r++)
{
scanf("%d\n", &stops);

int s;
for(s=1; s < stops; s++)
{
scanf("%4d\n", &route[s]);
}

maxfolge(stops);

if(0)
printf("Route %d has no nice parts\n", r);
else
printf("The nicest part of route %d is between stops %d and %d\n", r, bestStart, bestEnd);

}

return 0;
}

int maxfolge(int n)
{
int i, j, s ,total = INT_MIN, sum;
for(i=n-1; i >= 0; i--)
{
sum = 0;
for(j=i; j >= 0; j--)
{
sum += route[j];
// printf("i = %d, j = %d, sum = %d, total = %d\n", i,j,sum, total);
if(sum >= total)
{
bestEnd = j+1;
bestStart = i;
total = sum;
}
}
}

return total;
}