Maksymalna różnica

Question

tresc zadania: https://prnt.sc/leag8v

moj kod: http://www.wklejto.pl/655870

co zmienic, żeby zaliczyło zadanie ponieważ przekracza limit czasu

Answer 1

Spróbuj poprawić sam, a nie proś o gotowe!

A oto moja podpowiedź: Spróbuj znaleźć najmniejszą i największą liczbę algorytmem Quicksort, a potem odejmij. Powinno się zmieścić w czasie, u mnie posortowanie 100 000 elementowej tablicy z liczbami losowymi zajmuje ok. 0,017s.

Powodzenia !!!

Comments

Po co sortowac zeby znalezc min i max :D i jak by to mialo przyspieszyć program?

---

I tak musisz sprawdzić każdą liczę, a ten algorytm, chociaż pamięciożerny, to dla tablicy takich liczb jak w zadaniu posortowanie ich zajmie mu ok. 0,09s. Znacznie przyśpieszy to szybkość programu w stosunku do standardowej pętli iteracji. Przetestuj, algorytm jest np. na wikipedii, powinno się udać :) 

---

Twierdzisz ze sortowanie jest szybsze od pojedynczego przeiterowania po tablicy :p ?

---

Nie, ale skoro przeiterowanie tablicy w kodzie kolegi Szaradek jest za wolne, to może ten algorytm ? Jak pisałem, może to być szybsze.

Answer 2

Spróbuj może od razu przy wczytywaniu sprawdzać czy wczytana liczba jest maksimum albo minimum

Answer 3

#include <iostream>
 
using namespace std;
 
int main()
{
    int n,lmax,lmin, value;
    cin >> n;
    if(n>0){
      cin >> lmax;
      lmin = lmax;
    }
    for(int i=1; i<n; i++)
    {
        cin >> value;
        if(value > lmax) 
            lmax = value;
        else if(value < lmin) 
            lmin = value;
    }
    cout << lmax-lmin;
 
}

Nie potrzebujesz tablicy