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 2

Intrare

5

7 9 -6 1 -8

2

1 5

2 4 3

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 2921 - SumeSecv1

def validate_input(n, arr, m, pairs):

   if not(1 <= n <= 100000 and 1 <= m <= 500000 and len(arr) == n and len(pairs) == m):
       print("Datele nu corespund restricțiilor impuse.")
       return False
   for num in arr:
       if abs(num) > 10**9:
           print("Datele nu corespund restricțiilor impuse.")
           return False
   for i, j in pairs:
       if not (1 <= i <= j <= n):
           print("Datele nu corespund restricțiilor impuse.")
           return False
   print("Datele sunt introduse corect.")
   return True

def find_max_sum(n, arr, m, pairs):

   if not validate_input(n, arr, m, pairs):
       return

   max_sum = float('-inf')
   for i, j in pairs:
       curr_sum = sum(arr[i-1:j])
       if curr_sum > max_sum:
           max_sum = curr_sum

   print(max_sum)

if __name__ == "__main__":

   n = int(input())
   arr = list(map(int, input().split()))
   m = int(input())
   pairs = []
   for _ in range(m):
       i, j = map(int, input().split())
       pairs.append((i, j))
   find_max_sum(n, arr, m, pairs)

</syntaxhighlight>

Explicatie Rezolvare

Funcția `validate_input` este o funcție care primește ca parametrii dimensiunile listei de numere întregi, lista de numere întregi și lista de perechi de indici, verifica dacă datele introduse corespund restricțiilor impuse și afișează un mesaj corespunzător. Aceasta returnează `True` dacă datele sunt corecte și `False` în caz contrar.

Funcția `find_max_sum` primește aceleași parametrii ca și `validate_input`. Verifică dacă datele sunt introduse corect prin apelarea funcției `validate_input` și returnează `None` dacă datele nu sunt corecte. În caz contrar, calculează și afișează suma maximă dintre toate secvențele date de perechile de indici.

Funcția `main` citește datele de intrare, apelează funcția `find_max_sum` și afișează rezultatul.