Best Time to Buy and Sell Stock

+10

Kamu mendapatkan sebuah list prices, dengan prices[i] sebagai harga satu saham pada hari ke-i. Kamu boleh membeli satu saham pada suatu hari dan menjualnya pada hari berikutnya atau hari setelahnya. Kembalikan keuntungan terbesar yang bisa kamu dapatkan, atau 0 jika semua kemungkinan transaksi merugi.

Fungsi

maxProfit(prices: integer-array) → integer

pricesinteger-array: harga saham pada setiap hari, secara berurutan
Mengembalikaninteger: keuntungan terbesar dari satu pembelian dan penjualan setelahnya, atau 0

Batasan

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
Kamu melakukan paling banyak satu transaksi, dan kamu menjual pada hari setelah hari kamu membeli.

Contoh

Input: prices = [7, 2, 5, 9, 1, 4]
Output: 7
Penjelasan: Beli pada hari ke-1 dengan harga 2 dan jual pada hari ke-3 dengan harga 9 untuk mendapatkan keuntungan 7. Harga termurah, yaitu 1 pada hari ke-4, terjadi setelah harga 9, jadi penjualan terbaik setelahnya hanya menghasilkan 3.

Pertanyaan lanjutan

Bagaimana jika kamu boleh melakukan transaksi sebanyak yang kamu inginkan, sambil memegang paling banyak satu saham pada satu waktu?

Solusi

Kamu harus membeli sebelum menjual, jadi jawabannya bukan harga tertinggi dikurangi harga terendah. Untuk setiap hari saat kamu bisa menjual, pembelian terbaik adalah pada hari termurah sebelumnya. Dengan menyimpan harga termurah itu sambil melangkah maju, masalah ini bisa diselesaikan dalam satu kali lintasan.

Coba setiap pasangan beli dan jual

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Setiap transaksi memiliki hari pembelian dan hari penjualan setelahnya, jadi coba setiap pasangan dan simpan selisih terbesar. Memulai keuntungan terbaik dari 0 mencakup pilihan untuk tidak bertransaksi. Setiap transaksi yang diizinkan diperiksa, jadi jawabannya benar.

List berisi n harga memiliki sekitar n²/2 pasangan: 100,000 hari berarti sekitar 5 miliar pengurangan.

Algoritma

Tetapkan best ke 0.
Lakukan perulangan untuk setiap hari pembelian buy.
Untuk setiap hari tersebut, lakukan perulangan untuk setiap hari penjualan sell setelahnya.
Hitung prices[sell] dikurangi prices[buy], lalu simpan hasilnya di best jika nilainya lebih besar.
Kembalikan best.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

Satu kali penelusuran dengan harga terendah sejauh ini

Intuisi

Tetapkan hari penjualan i. Hari terbaik untuk membeli adalah hari dengan harga termurah hingga i, jadi transaksi terbaik yang berakhir pada hari i menghasilkan prices[i] dikurangi harga terendah sejauh ini. Setiap hari penjualan dipasangkan dengan hari pembelian terbaiknya, jadi profit terbesar dari semua pasangan itu adalah jawabannya. Pada hari yang menetapkan harga terendah baru, profitnya 0, sama seperti tidak melakukan transaksi.

Penelusuran ini membaca setiap harga sekali dan menyimpan dua angka, lowest dan best: waktu O(n) dan ruang O(1).

Algoritma

Atur lowest ke harga pertama dan best ke 0.
Telusuri harga sesuai urutan.
Jika harga saat ini lebih rendah daripada lowest, jadikan harga tersebut nilai baru lowest.
Hitung harga saat ini dikurangi lowest, lalu simpan hasilnya di best jika nilainya lebih besar.
Kembalikan best.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

Jebakan dan kasus tepi

Mengembalikan harga tertinggi dikurangi harga terendah. Dalam [7, 2, 5, 9, 1, 4] hasilnya 8, tetapi 1 muncul setelah 9. Jawabannya adalah 7.
Membiarkan jawaban menjadi negatif. Dalam [9, 7, 4, 3, 1] selisih terbaik adalah -1. Mulai best dari 0, bukan dari selisih pertama.
Memulai lowest dari 0. Setiap keuntungan kemudian sama dengan harganya, jadi [9, 7, 4, 3, 1] menghasilkan 9. Mulai dari harga pertama.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Best Time to Buy and Sell Stock?

Solusi satu lintasan membutuhkan waktu O(n) untuk n hari, karena solusi ini membaca setiap harga satu kali, dan ruang tambahan O(1): harga terendah sejauh ini dan keuntungan terbaik. Mencoba setiap pasangan hari membutuhkan waktu O(n²).

Mengapa tidak mengurangi harga terendah dari harga tertinggi?

Harga terendah mungkin muncul setelah harga tertinggi, dan kamu harus membeli sebelum menjual. Dalam [7, 2, 5, 9, 1, 4], angka 1 muncul setelah angka 9, jadi transaksi terbaik yang diizinkan adalah membeli di harga 2 dan menjual di harga 9 untuk mendapatkan keuntungan 7.

Apakah Best Time to Buy and Sell Stock merupakan masalah pemrograman dinamis?

Kamu bisa membacanya dengan kedua cara. Harga terendah sejauh ini adalah state kecil yang kamu perbarui setiap hari, inilah sudut pandang pemrograman dinamis. Memasangkan setiap penjualan dengan hari sebelumnya yang paling murah adalah sudut pandang greedy. Keduanya menghasilkan kode satu lintasan yang sama.

def maxProfit(prices):
    # Tulis kodemu di sini

Tes #1

Tes #2

Argumen

prices = [7, 2, 5, 9, 1, 4]

Output yang diharapkan