2220 - DifMax

Sursa: 2220 - DifMax

---

Cerinţa

Se consideră un șir a[1], a[2], …, a[n] de numere întregi. Să se determine diferența maximă de forma a[i] - a[j], unde 1 ≤ i < j ≤ n.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.

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 va afișa un singur număr întreg reprezentând diferența maximă cerută. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ n ⩽ 100.000
• -1 000 000 000 ⩽ a[i] ⩽ 1 000 000 000

Exemple

Exemplul 1

Intrare

8

3 5 2 7 6 3 9 8

Ieșire

Datele sunt introduse corect.

4

Explicație exemplul 1

Diferența maximă 4 se obține din a[4]-a[6]=7-3=4.

Exemplul 2

Intrare

1234

1 2 3

Ieșire

Datele nu corespund restricțiilor impuse.

Rezolvare

# 2220 DifMax

def afis_diferenta_maxima(n, a):
    diferenta_maxima = -1000000000
    for i in range(n):
        for j in range(i+1, n):
            if a[i] - a[j] > diferenta_maxima:
                diferenta_maxima = a[i] - a[j]
    print(diferenta_maxima)


def citire_conform_restrictiilor(n, a):
    if n < 1 or n > 100000:
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    for element in a:
        if element >= 1000000000 or element < -1000000000:
            print("Datele nu corespund restricțiilor impuse.")
            exit()
    if n != len(a):
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    print("Datele sunt introduse corect.")


if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))
    citire_conform_restrictiilor(n, a)
    afis_diferenta_maxima(n, a)

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția  afis_diferenta_maxima(n, a) și funcția citire_conform_restrictiilor(n, a), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 26) după citirea numărului n (linia 27) și celor n numere pe care le vom pune în șirul „a” (linia 28).
   După ce am citit elementele, se va apela funcția citire_conform_restrictiilor(n, a) care primește doi parametri: vectorul „a” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă lungimea vectorului n este între 1 și 100000 (linia 13), dacă elementele vectorului sunt cuprinse între -1000000000 și 1000000000 (liniile 16, 17) și dacă n este lungimea vectorului „a” (linia 20). Dacă oricare dintre condiții este încălcată, se va afișa mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa mesajul „Datele sunt introduse corect.” (linia 23) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția afis_diferenta_maxima(n, a) care primește ca parametrii vectorul „a” și dimensiunea sa „n”. În această funcție se inițializează variabila diferenta_maxima cu -10000000000 (valoarea cât mai mică pentru a fi înlocuită pentru orice valoare din șirul a) și se folosesc două bucle for pentru a parcurge toate combinațiile posibile de două numere din șir (liniile 5, 6, în a doua buclă pornim de la i+1 deoarece în problemă se spune că indicii i, j au proprietatea că i < j). În interiorul buclei for, dacă diferența dintre cele două numere este mai mare decât diferenta_maxima (un număr inițial foarte mic), atunci diferenta_maxima este actualizată cu noua valoare. La sfârșitul funcției, după parcurgerea tuturor combinațiilor, în variabila diferenta_maxima vom avea valoarea maximă a diferențelor, care va fi afișată pe ecran utilizând funcția print.