Cod sursa(job #2849142)

Utilizator miHai231Mihai Mandragiu miHai231 Data 14 februarie 2022 17:13:19
Problema Subsecventa de suma maxima Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
using namespace std;

const int N = 6000000;

long long sp[N + 1], maxx;

int main()
{
    ifstream in("ssm.in");
    ofstream out("ssm.out");
    int st_max = 1, dr_max = 1, n, x, suma;
    in >> n;
    for (int i = 1; i <= n; i++)
    {
        in >> x;
        sp[i] = sp[i - 1] + x;
    }
    in.close();
    for (int dr = 1; dr <= n; dr++)
    {
        int min_poz = 0;
        for (int i = 1; i < dr; i++)
            if (sp[min_poz] > sp[i])
                min_poz = i;
        suma = sp[dr] - sp[min_poz];
        if (suma > maxx)
        {
            maxx = suma;
            st_max = min_poz + 1;
            dr_max = dr;
        }
    }
    out << maxx << " " << st_max << " " << dr_max;
    out.close();
    return 0;
}