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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou numărul S, reprezentând suma maximă determinată, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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 1

Intrare

5

7 9 -6 1 -8

3

1 3

4 2

2 5

Ieșire

Datele sunt introduse correct.

10

Exemplu 1

Intrare

5 1 2

7 9 -6 1 -8

3 3 3

1 3

4 2 3

2 5 4

Ieșire

Datele nu corespund restricțiilor impuse.

2 3 4

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

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:
       if i >= j or i < 1 or j > n:
           print("Datele nu corespund restricțiilor impuse.")
           return
       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
       print(suma_max_subsecventa)
           

if __name__ == '__main__':

   n, a, m, perechi = citire()
   if 1 <= n <= 100 and all(0 <= x < 1000 for x in a) and 1 <= m <= 100:
       print("Datele sunt introduse corect.")
       calc_suma_max(n, a, m, perechi)
   else:
       print("Datele nu corespund restricțiilor impuse.")

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