Cod sursa(job #2675278)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 21 noiembrie 2020 12:01:43
Problema Subsecventa de suma maxima Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <fstream>
using namespace std;

ifstream fin("ssm.in");
ofstream fout("ssm.out");

int sume_partiale[6000005], suma_minima, suma_max = -2000000000, n, secv, stocare[6000005], stanga, stanga_min, dreapta;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> stocare[i];
    for (int i = 1; i <= n; ++i)
        sume_partiale[i] = stocare[i] + sume_partiale[i - 1];
    suma_minima = sume_partiale[0];
    for (int i = 1; i <= n; ++i)
    {
        secv = sume_partiale[i] - suma_minima;
        if (suma_max < secv)
        {
            stanga = stanga_min;
            suma_max = secv;
            dreapta = i;
        }
        if (suma_minima > sume_partiale[i])
        {
            suma_minima = sume_partiale[i];
            stanga_min = i + 1;
        }
    }
    fout << suma_max << " " << stanga << " " << dreapta;
    return 0;
}