Question

Cerinţa
Se dă un şir cu n elemente, numere întregi. Determinaţi secvenţa de elemente cu suma maximă.

Date de intrare
Fişierul de intrare secvsummax.in conţine pe prima linie numărul n; urmează cele n elemente ale şirului, dispuse pe mai multe linii şi separate prin spaţii.

Date de ieşire
Fişierul de ieşire secvsummax.out va conţine pe prima linie numerele p şi u, separate printr-un spaţiu, reprezentând poziţia de început şi de sfârşit a secvenţei determinate.

Restricţii şi precizări
1 ≤ n ≤ 100000
elementele şirului vor avea cel mult 4 cifre şi sunt numerotate de pa 1 la n
daca şirul conţine mai multe secvenţe de suma maximă, se va determina cea cu indicele de început cel mai mic, iar în caz de egalitatea cea mai surtă
şirul va conţine cel puţin un element pozitiv

Exemplu
secvsummax.in

10
-4 1 -5 1 4 -2 2 3 -4 4
secvsummax.out

4 8
Explicaţie
Secvenţa 1 4 -2 2 3 are suma 8, şi este suma maximă pentru toate secvenţele care se pot forma.

Answer 1

#include<cstdio>
#define oo 0x3f3f3f3f
using namespace std;

int n, x, bestSum, sumSoFar, Begin, End, i, idx;

int main()
{
    FILE *fin, *fout;
    fin = fopen("secvsummax.in","r");
    fout = fopen("secvsummax.out","w");
    fscanf(fin,"%d",&n);
    sumSoFar = 0;
    bestSum = -oo;
    Begin = End = idx = 1;
    for(i=1; i<=n; i++)
    {
        fscanf(fin,"%d",&x);
        if(sumSoFar < 0)
        {
            sumSoFar = x;
            idx = i;
        }
        else sumSoFar += x;
        if(sumSoFar > bestSum)
        {
            bestSum = sumSoFar;
            Begin = idx;
            End = i;
        }
    }
    fprintf(fout,"%d %d\n",Begin,End);
    fclose(fin);
    fclose(fout);
    return 0;
}