Cod sursa(job #2601362)

Utilizator LordVPetrescu Vladimir-Ioan LordV Data 14 aprilie 2020 13:09:47
Problema Subsecventa de suma maxima Scor 35
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int main()
{
    ifstream fin("ssm.in");
    ofstream fout("ssm.out");
    int n;
    int beg;
    int endd;
    int idx;
    long long v[100000];
    long long best[10000];
    long long maxi = 0;

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

    if(0<v[0]){
        best[0] = v[0];
    }
    else{
        best[0] = 0;
        idx = 0;
    }

    for(int i=1;i<n;i++){
        if(0<best[i-1]+v[i]){
            best[i] = best[i-1]+v[i];
            if(best[i]>maxi){
                maxi = best[i];
                beg = idx;
                endd = i+1;
            }
        }
        else{
            best[i] = 0;
            idx = i+2;
        }
    }

    fout<<maxi<<" "<<beg<<" "<<endd;
}