# PBinfo #2220 – DifMax – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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

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

## Cod sursă C++

```cpp
/// 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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2220)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2220/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2220/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)