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.

14

Rezolvare

Rezolvare ver. 1

# 2921 - SumeSecv1
def suma_maxima(n, nr, m, perechi):
    # Verificăm restricțiile impuse
    if n < 1 or n > 100000 or m < 1 or m > 500000:
        return "Datele nu corespund restrictiilor impuse."
    for i, j in perechi:
        if i < 1 or i > n or j < 1 or j > n:
            return "Datele nu corespund restrictiilor impuse."
    
    # Calculăm suma maximă
    s_max = 0
    s_curenta = 0
    for i in range(n):
        s_curenta += nr[i]
        if s_curenta < 0:
            s_curenta = 0
        elif s_curenta > s_max:
            s_max = s_curenta
    
    for i, j in perechi:
        s = sum(nr[i-1:j])
        if s > s_max:
            s_max = s
    
    return s_max

if __name__ == "__main__":
    # Citim datele de intrare
    n = int(input())
    nr = list(map(int, input().split()))
    m = int(input())
    perechi = [tuple(map(int, input().split())) for _ in range(m)]
    
    # Apelăm funcția și afișăm rezultatul
    rezultat = suma_maxima(n, nr, m, perechi)
    if isinstance(rezultat, str):
        print(rezultat)
    else:
        print("Datele sunt introduse corect.")
        print(rezultat)

Explicatie Rezolvare

Funcția citeste_date(): această funcție are rolul de a citi datele de la tastatură și de a returna valorile citite sub forma a două liste. Mai întâi se citește numărul n și apoi elementele șirului a, apoi numărul de perechi m și apoi perechile de indici i și j. Valorile citite sub forma de liste sunt returnate într-un tuplu de forma (a, indici). Funcția suma_maxima(a, indici): această funcție primește ca argumente lista a cu elementele șirului și lista indici cu perechile de indici și are rolul de a calcula suma maximă dintre toate secvențele posibile determinate de perechile de indici. Pentru fiecare pereche de indici (i, j), se calculează suma elementelor din secvența determinată de acești indici, iar apoi se determină suma maximă dintre toate aceste sume. Funcția returnează această suma maximă.