Cod sursa(job #409525)

Utilizator andreirRoti Andrei andreir Data 3 martie 2010 18:34:51
Problema Subsecventa de suma maxima Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
#define minf -1999999999
using namespace std;
vector<int>v;
int main()
{
	int n,i,j,x,smax=minf,ssm=minf,slm=minf,sm=minf;
	freopen("ssm.in","r",stdin);
	freopen("ssm.out","w",stdout);
	//citeste n si vectorul
	v.push_back(smax);
	scanf("%d",&n);	for(i=1;i<=n;i++){	scanf("%d",&x);		v.push_back(x);}
	
	//rezolva
	//suma maxima
	//ssm inceput secventa de suma max
	//ssl lungima secventa de suma max
	
	for(i=1;i<=n;++i)
	{
		sm=v[i]; 
		if(sm>smax)				   {	smax=sm;	ssm=i;	slm=1;   }
		else if(sm==smax && i<ssm) {				ssm=i;	slm=1;   }
		else if(i==ssm && 1<slm)   							slm=1;   
		
		for(j=i+1;j<n;j++)
		{
			sm=sm+v[j];
			if(sm>smax)				   	{smax=sm;	ssm=i;	slm=j-i; }
			else if(sm==smax && i<ssm)  {			ssm=i;	slm=j-i; }
			else if(i==ssm && (j-i)<slm)   					slm=j-i;    
		}
	}
	printf("%d %d %d\n",smax,ssm,ssm+slm);
	return 0;
}