Untung Terbesar
Tentukan keuntungan terbesar dari membeli lalu menjual sekali.
Pedagang cabai di pasar induk mencatat harga cabai per kilogram selama N hari. Ia boleh membeli sekali, lalu menjual sekali di hari berikutnya atau setelahnya. Berapa keuntungan terbesar yang bisa ia dapat?
Masukan
Baris pertama berisi N (1 sampai 30000). Baris kedua berisi N bilangan bulat positif, harga tiap hari.
Keluaran
Keuntungan terbesar yang mungkin. Bila harga terus turun sehingga tidak ada cara untung, tampilkan 0.
Contoh masukan dan keluaran
Contoh 1
Masukan
6 7 1 5 3 6 4
Keluaran
5
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Memeriksa semua pasangan hari beli dan hari jual terlalu lama untuk 30000 hari.
Petunjuk 2
Telusuri hari satu per satu sambil mengingat harga termurah sejauh ini. Untung terbaik bila menjual hari ini adalah harga hari ini dikurangi harga termurah itu.