2921 - SumeSecv1

Sursa: 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

# 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)

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ț.