Se consideră un șir a[1], a[2], …, a[n] de numere întregi.

Cerința

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

Programul va afișa pe ecran un singur număr întreg reprezentând diferența maximă cerută.

Restricții și precizări

1 ≤ n ≤ 100 000
-1 000 000 000 ≤ a[i] ≤ 1 000 000 000

Exemplu

Intrare

8
3 5 2 7 6 3 9 8

Ieșire

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema DifMax:

/// Complexitate O(n)
#include <bits/stdc++.h>
#define nmax 100002
using namespace std;

int a[nmax], s[nmax], d[nmax], n;

int main()
{
    int i, M;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];

    /// calcul maxime partiale de la stanga la dreapta:
    /// s[i] = max(a[1], a[2], ..., a[i])
    s[1] = a[1];
    for (i = 2; i <= n; i++)
        s[i] = max(s[i - 1], a[i]);

    /// calcul minime partiale de la dreapta la stanga:
    /// d[i] = min(a[i], a[i+1], ..., a[n])
    d[n] = a[n];
    for (i = n - 1; i >= 1; i--)
        d[i] = min(d[i + 1], a[i]);

    /// Pentru pozitia i, diferenta maxima este data de diferenta dintre
    /// cea mai mare valoare din a[1..i], adica s[i], si cea mai mica
    /// valoare din a[i+1..n], adica d[i+1].
    M = s[1] - d[2];
    for (i = 2; i < n; i++)
        M = max(M, s[i] - d[i + 1]);

    cout << M;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2220 DifMax

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2220 DifMax de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2220 DifMax