Cod sursa(job #3238279)

Utilizator Alex21Ungureanu Alexandru Alex21 Data 23 iulie 2024 17:41:29
Problema Subsecventa de suma maxima Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.71 kb
#include <fstream>
#include <climits>
using namespace std;

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

#define N 6000005

int sir[N] = {0};
int sp[N] = {0};

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

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

    int smax = INT_MIN;
    int st = 1;
    int dr = 1;
    int j = 1;

    for (int i = 1; i <= n; i++) {
        if (sp[i] > sp[dr]) {
            dr = i;
            while (j <= i) {
                if(sp[j - 1] < sp[st - 1]) {
                    st = j;
                }

                j++;
            }

            smax = sp[dr] - sp[st - 1];
        }
    }

    fout << smax << ' ' << st << ' ' << dr;
}