Question

Problema #1804 ursulet pbinfo

Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.
Cerința

Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.
Date de intrare

Fișierul de intrare ursulet.in conține pe prima linie numărul N, ce semnifică numărul de zone traversate de ursuleţ. Pe linia următoare se află N numere întregi, altitudinile zonelor.
Date de ieșire

Fișierul de ieșire ursulet.out va conține pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță.
Restricții și precizări

1 ≤ n ≤ 100000
-1000 ≤ a ≤ 1000, a fiind altitudinea unei zone
Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.


Exemplu

ursulet.in

6
-5 0 3 1 -4 2

ursulet.out

4
2 4

Answer 1

#include <fstream>

using namespace std;

int v[100001];

int main(){

int n;

   ifstream fin("ursulet.in");

   ofstream fout("ursulet.out");

   

   fin >> n;

   for(int i = 1; i <= n; i++){

    fin >> v[i];

   }

   fin.close();

   int max = -1, mb = 0, me = 0, b = 0, e = 0, s = 0;

   for(int i = 1; i <= n; i++){

       if(s < 0) {s = v[i];b = i;e = i;}

       else {s += v[i]; e = i;}

       if(s > max){

        max = s;

           mb = b;

           me = e;

       }

   }

   fout << max << '\n' << mb << ' ' << me;

   fout.close();

}

E un clasic: suma partiala maxima pe vector.