Cod sursa(job #3246700)

Utilizator agent_zebra54Morariu Radu Dimitri agent_zebra54 Data 4 octombrie 2024 09:22:17
Problema Subsecventa de suma maxima Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 6000006;

int s[Nmax], v[Nmax];

int main()
{
    int n;
    fin >> n;

    for (int i = 1; i <= n; ++i)
    {
        fin >> v[i];
        s[i] = s[i - 1] + v[i];
    }

    int mini_sum = 0, bestSum = -2000000010;
    int poz_st = 0, poz_dr = 1, poz_inceput = 0;

    for (int i = 1; i <= n; ++i)
    {
        int current_sum = s[i] - mini_sum;

        if (current_sum > bestSum || (current_sum == bestSum && i - poz_inceput < poz_dr - poz_st))
        {
            bestSum = current_sum;
            poz_st = poz_inceput;
            poz_dr = i;
        }

        if (s[i] < mini_sum)
        {
            mini_sum = s[i];
            poz_inceput = i;
        }
    }

    fout << poz_st + 1 << " " << poz_dr;

    return 0;
}