Kapan membeli/menjual saham? Mengingat sebuah array berisi harga harian suatu saham. Cobalah untuk mencari keuntungan maksimal.

Input: [20,10,30,44,26,40,50]
Output: 58
Explanation: 
Buy on day 2 and sell on day 4, profit = 44-10 = 34.
Buy on day 5 and sell on day 7, profit = 50-26 = 24.

Proses berpikir:

Dari pertanyaan sebelumnya Pindahkan Nol, kita tahu bahwa setidaknya kita ingin mengulang array input satu kali, sehingga Kompleksitas Waktunya menjadi O(n). Kita dapat menggunakan struktur data tambahan (yaitu Array/Linked List/Map/Set) untuk membantu kita menyimpan keuntungan sehari-hari, dan menjumlahkan keuntungan di akhir. Tapi tunggu dulu, apakah kita benar-benar peduli pada hari apa kita mendapat untung berapa? Atau bisakah kita menjumlahkan total keuntungan sambil mengulang array input?

Larutan:

makeProfit(prices) {
    // Use a constant space O(1) to record total profit.
    let profit = 0;
    // While looping through the input array, we calculate the profit and add it to the sum.
    for(let i = 0; i < prices.length - 1; i++) {
        profit += Math.max(0, prices[i + 1] - prices[i]);
    }
    return profit;
};

Catatan Utama:

  1. Menghemat Ruang
  2. Bagaimana cara melacak & menghitung keuntungan dari array input?

Apa pertanyaan selanjutnya?

Temukan Duplikat — Mengingat serangkaian angka, kembalikan nilai benar jika ada angka yang muncul lebih dari sekali dalam larik, jika tidak, kembalikan salah. (“proses berpikir dan solusi»)

Sebelum kamu pergi -

Tidak ada cara yang lebih baik untuk mendukung saya selain mengikuti saya di Medium (Victor Lin»). Beri tahu saya bahwa saya harus menulis lebih banyak!

Tahukah Anda bahwa Anda bisa memberikan hingga 50 👏 dengan menekan tombol 👏? Cobalah jika Anda benar-benarmenyukai artikel ini!