View source for 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 == 
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>
# 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.