Cod sursa(job #292259)

Utilizator alex23alexandru andronache alex23 Data 30 martie 2009 22:04:31
Problema Subsecventa de suma maxima Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <limits.h>

using namespace std;

FILE *f = fopen("ssm.in", "r"), *g = fopen("ssm.out", "w");

int *a, *b, N, li = 0, ls = 0, sMax = INT_MIN, sTemp = 0, liT = 0, lsT = 0, l = 0;
char *sir;

int main()
{
	fscanf(f, "%d\n", &N);
	a = new int[N];
	sir = new char[30000000];
	/*
	for (int i = 0; i < N; ++i)
	{
		fscanf(f, "%d", &a[i]);
	}
	*/
	fgets(sir, 30000000, f);
	int nr = 0, negativ = 0;
	while (*sir != '\0')
	{
		if (*sir == '-')
		{
			negativ = 1;
			*sir++;
		}
		if ((*sir >= '0') && (*sir <= '9'))
		{
			nr = nr + *sir - '0';
		}
		else
		{
			if (negativ)
			{
				a[l] = -nr;
			}
			else
			{
				a[l] = nr;
			}
		    l++;
			nr = 0;
			negativ = 0;
		}
		*sir++;
	}
	fclose(f);
    
	for (int i = 0; i < N; ++i)
	{
		if (a[i] > 0)
		{
			sTemp += a[i];
		}
		if (a[i] == 0)
		{
			if (sTemp > sMax)
			{
				li = liT, ls = i - 1, sMax = sTemp;
			}
		}
		if (a[i] < 0)
		{
			if (a[i] + sTemp < 0)
			{
				if (a[i] > sMax)
				{
					li = liT, ls = i, sMax = a[i];
					liT = i + 1;
					sTemp = 0;
				}
				else
				{
					liT = i + 1;
					sTemp = 0;
				}
			}
			else
			{
				if (sTemp > sMax)
				{
					sMax = sTemp, li = liT, ls = i - 1;
				}
				if (a[i] + sTemp >= 0)
				{
					sTemp += a[i];
				}
			}
		}
	}
	
	if ((sTemp > sMax) && (sTemp != 0))
	{
		sMax = sTemp, li = liT, ls = N - 1;
	}
	
	/*
	b = new int[N];
	b[0] = a[0];
	for (int i = 1; i < N; ++i)
	{
		b[i] = max(a[i], b[i - 1] + a[i]);
	}
	for (int i = 0; i < N; ++i)
	{
		if (b[i] > sMax)
		{
			sMax = b[i];
			ls = i;
		}
	}
	int i = ls;
	while (b[i] > 0)
	{
		cout << b[i] << " ";
		i--;
		
	}
	*/
	
	//fprintf(g, "%d %d %d", sMax, i + 2, ls + 1);
	fprintf(g, "%d %d %d", sMax, li + 1, ls + 1);
	fclose(g);
}