Question

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.

Answer 1

Cerința nu explică ce se întâmplă dacă n = 1.

Complexitate timp: O(N)
Complexitate spațiu: O(1)

#include <iostream>

using namespace std;

int main() {
  int n, ai, aj;
  cin >> n >> ai;
  int difMax = -2000000000;
  for (int j = 1; j < n; j++) {
    cin >> aj;
    difMax = max(difMax, ai - aj);
    ai = max(ai, aj);
  }
  cout << difMax;
  return 0;
}