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
Pe urmatorul program iau 90 de puncte:
#include <iostream>
using namespace std;
int n,dif,v[100005],s[100005],d[100005],maxi,mini,ok=1;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
if(maxi<v[i])
s[i]=v[i], maxi=v[i];
else
s[i]=maxi;
if(v[i]<v[i-1])             
ok=0;
}
mini=v[n];
for(int i=n;i>=1;i--)
{
if(mini>v[i])
d[i]=v[i], mini=v[i];
else
d[i]=mini;
}
for(int i=1;i<=n-1;i++)
{
if(dif< s[i]-d[i+1])
dif=s[i]-d[i+1];
}
if(ok)
cout<<v[n-1]-v[n];
else
cout<<dif;
return 0;
}

Answer 1

1. Felicitari ca macar ai incercat sa rezolvi.

2. Te complici prea mult cu 99999 de vectori si variabile, mai ales globale, incearca sa nu folosesti variabile globale cand nu e neaaparat nevoie.

#include <iostream>
using namespace std;
int main()
{
    int n, temp, min, max;    
   
    cin >> n;
    
    cin >> temp;

    min = max = temp;

    for (int i = 2; i <= n; i++)
    {
        cin >> temp;

        if (temp > max)
            max = temp;

        if (temp < min)  
            min = temp;
    }

    cout << max - min;

    return 0;
}

Nu ai nevoie de vector. Diferenta maxima oricum va fi mereu cel mai mare element minus cel mai mic, deci ai doar de calculat min si max din sirul ala de numere. Iar min si max pot fi calculate direct in timp ce citesti vectorul, nici macar nu trebuie sa retii elementele pe care deja le-ai citit, ai nevoie doar de o variabila n ca sa stii cate numere citesti, si o variabila temp in care se retii ultimul numar citit doar cat sa il verifici cu min si max, apoi nu mai ai nevoie de el. 

Dupa cum vezi am citit n, apoi am citit primul nr, si am facut si min si max sa fie acel nr, pentru ca infara cazului in care tot vectorul e facut DOAR din acel numar, ele or sa se modifice cand or sa citeasca ceva mai mare sau mai mic. 

Deci doar citeesc cate un numar, actualizez min si max la nevoie, iar la sfarsit afisez diferenta, nu am nevoie nici de o variabila noua pt diferenta.

Edit: Am atasat sursa noua.