Annettuna on lista lukuja ja tehtäväsi on selvittää, mikä on suurin etäisyys kahden luvun välillä. Esimerkiksi listalla $[4,5,2,1,2]$ suurin etäisyys on $4$, joka saadaan, kun valitaan luvut $5$ ja $1$.

Listan jokainen alkio on kokonaisluku välillä $1 \dots 10^9$ ja listassa on enintään $10^5$ alkiota. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Python

Toteuta tiedostoon maxdist.py funktio find, joka ilmoittaa suurimman etäisyyden.

def find(t):
    # TODO

if __name__ == "__main__":
    print(find([4,5,2,1,2])) # 4
    print(find([1,2,3,4])) # 3
    print(find([1])) # 0
    print(find([1,2,100,5])) # 99

Java

Toteuta tiedostoon MaxDist.java metodi find, joka ilmoittaa suurimman etäisyyden.

public class MaxDist {
    public int find(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        MaxDist m = new MaxDist();
        System.out.println(m.find(new int[] {4,5,2,1,2})); // 4
        System.out.println(m.find(new int[] {1,2,3,4})); // 3
        System.out.println(m.find(new int[] {1})); // 0
        System.out.println(m.find(new int[] {1,2,100,5})); // 99
    }
}