Cod sursa(job #679024)

Utilizator alexdmotocMotoc Alexandru alexdmotoc Data 12 februarie 2012 17:42:11
Problema Subsecventa de suma maxima Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
//O (N ^ 2)

#include <cstdio>
#include <iostream>

using namespace std;

#define maxN 6000005
#define INF 0x3f3f3f3f

int N , x[maxN] , s[maxN];

int main ()
{
	freopen ("ssm.in" , "r" , stdin);
	freopen ("ssm.out" , "w" , stdout);
	
	scanf ("%d" , &N);
	
	for (int i = 1 ; i <= N ; ++i)
	{
		scanf ("%d" , &x[i]);
		
		s[i] = s[i - 1] + x[i];
	}
	
	int sol = -INF , start , stop;
	
	for (int i = 1 ; i <= N ; ++i)
		for (int j = 0 ; j < i ; ++j)
		{
			int aux = s[i] - s[j];
			
			if (aux > sol)
			{
				sol = aux;
				stop = i;
				start = j + 1;
			}
		}
	
	printf ("%d %d %d" , sol , start , stop);
	
	return 0;
}