// PR Bab 11, tantangan -- pembahasan.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int lambat(int a[], int n) {
    int terbaik = -2000000000;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (a[j] - a[i] > terbaik) terbaik = a[j] - a[i];
    return terbaik;
}

int cepat(int a[], int n) {
    int terbaik = -2000000000;
    int terkecil = a[0];
    for (int j = 1; j < n; j++) {
        if (a[j] - terkecil > terbaik) terbaik = a[j] - terkecil;
        if (a[j] < terkecil) terkecil = a[j];
    }
    return terbaik;
}

const int BESAR = 50000;
int deret[BESAR];

int main() {
    srand(2024);

    // 1. penguji acak pada deret kecil
    for (int uji = 1; uji <= 2000; uji++) {
        int n = rand() % 6 + 2;            // n minimal 2
        int a[10];
        for (int i = 0; i < n; i++) a[i] = rand() % 21 - 10;

        if (lambat(a, n) != cepat(a, n)) {
            cout << "berbeda pada uji ke-" << uji << "\n";
            return 0;
        }
    }
    cout << "2000 uji cocok\n";

    // 2. pengukuran waktu pada deret besar
    for (int i = 0; i < BESAR; i++) deret[i] = rand() % 1000000;

    clock_t t0 = clock();
    int h1 = lambat(deret, BESAR);
    double d1 = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();
    int h2 = cepat(deret, BESAR);
    double d2 = (double)(clock() - t0) / CLOCKS_PER_SEC;

    cout << "lambat: " << h1 << " (" << d1 << " detik)\n";
    cout << "cepat : " << h2 << " (" << d2 << " detik)\n";
    return 0;
}