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)

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