Editing 2921 - SumeSecv1

Sursa: [https://https://www.pbinfo.ro/probleme/2921/sumesecv1 2921 - SumeSecv1]
----
== Cerinţa ==
Se dă un șir cu n elemente numere întregi, numerotate de la 1 la n și m perechi de indici i j. Pentru fiecare pereche de indici se calculează suma elementelor din secvență determinată de cei doi indici. Afișați suma maximă obținută.
== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi n numere întregi, apoi m și m perechi i j.


== Date de ieșire == 
Programul va afișa pe ecran numărul S, reprezentând suma maximă determinată.

== Restricţii şi precizări ==
* 1 ≤ n ≤ 100.000;
* 1 ≤ m ≤ 500.000;
* 1 ≤ i,j ≤ n;
cele n elemente ale șirului vor avea cel mult nouă cifre.

== Exemplu ==
; Intrare
: 5
: 7 9 -6 1 -8
: 3
: 1 3
: 4 2
: 2 5
; Ieșire
: 10

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 2921 - SumeSecv1
def citire():
    n = int(input())
    a = list(map(int, input().split()))
    m = int(input())
    perechi = []
    for i in range(m):
        perechi.append(tuple(map(int, input().split())))
    return n, a, m, perechi


def calc_suma_max(n, a, m, perechi):
    suma_maxima = 0
    for i, j in perechi:
        suma_curenta = 0
        suma_max_subsecventa = float('-inf')
        for k in range(i-1, j):
            suma_curenta += a[k]
            if suma_curenta > suma_max_subsecventa:
                suma_max_subsecventa = suma_curenta
            if suma_curenta < 0:
                suma_curenta = 0
        if suma_max_subsecventa > suma_maxima:
            suma_maxima = suma_max_subsecventa
    return suma_maxima


def validare(suma_maxima):
    assert suma_maxima >= -9000000000 and suma_maxima <= 9000000000


if __name__ == '__main__':
    n, a, m, perechi = citire()
    suma_maxima = calc_suma_max(n, a, m, perechi)
    print(suma_maxima)
    validare(suma_maxima)

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire citește datele de intrare și le returnează într-o tuplă.
Funcția calc_suma_max calculează suma maximă a unei subsecvențe pentru fiecare pereche de indici și returnează suma maximă dintre toate sumele calculate.
Funcția validare verifică dacă suma maximă se încadrează în limitele impuse de enunț.
În funcția main, apelăm funcțiile citire, calc_suma_max, print și validare în ordinea specificată în enunț.