Best Time to Buy and Sell Stock: Dari Brute Force ke One-Pass O(n)

Soal

Diberikan array prices di mana prices[i] adalah harga saham pada hari ke-i. Tugas kita: cari maximum profit dari satu kali transaksi — beli di satu hari, jual di hari setelahnya. Kalau tidak ada profit yang mungkin (harga selalu turun), return 0.

Constraints:

• 1 <= prices.length <= 10⁵
• 0 <= prices[i] <= 10⁴

Contoh dari soal:

Input:  prices = [7, 1, 5, 3, 6, 4]
Output: 5

Beli hari ke-2 (harga = 1), jual hari ke-5 (harga = 6), profit = 6 - 1 = 5.

Input:  prices = [7, 6, 4, 3, 1]
Output: 0

Tidak ada transaksi yang menghasilkan profit — harga cuma turun terus.

Intuisi Awal — Brute Force

Pikiran pertama yang muncul: coba semua kemungkinan beli-dan-jual.

func maxProfit(prices []int) int {
    maxProfit := 0
    n := len(prices)
    for buy := 0; buy < n; buy++ {
        for sell := buy + 1; sell < n; sell++ {
            profit := prices[sell] - prices[buy]
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }
    return maxProfit
}

Logikanya sederhana: untuk setiap hari buy, coba semua hari sell setelahnya. Hitung profit, ambil yang terbesar.

Kompleksitas: O(n²) — nested loop penuh. Untuk n = 10⁵, ini jalan ~10¹⁰ iterasi. Tidak lolos.

Observasi Kunci

Perhatikan ulang contoh: [7, 1, 5, 3, 6, 4]

Untuk setiap calon hari jual, profit maksimum didapat kalau kita beli di harga terendah sebelum hari itu.

Maksimum profit: max(0, 4, 2, 5, 3) = 5. Cocok dengan output.

Pola: Track Minimum Sambil Scan

Dari tabel di atas kita sadar: kita tidak perlu nested loop. Cukup sekali jalan dari kiri ke kanan, sambil mencatat dua hal:

1. Harga terendah yang pernah kita lihat sejauh ini (min_price)
2. Profit maksimum yang bisa kita dapat jika jual di harga saat ini (max_profit)

Di setiap langkah i:

• Profit jika jual sekarang = prices[i] - min_price
• Update max_profit jika profit ini lebih besar
• Update min_price jika prices[i] lebih kecil dari min_price

Solusi Optimal — One-Pass O(n)

func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0

    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else {
            profit := price - minPrice
            if profit > maxProfit {
                maxProfit = profit
            }
        }
    }

    return maxProfit
}

Atau versi yang lebih ringkas:

func maxProfit(prices []int) int {
    minPrice := math.MaxInt32
    maxProfit := 0

    for _, price := range prices {
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price-minPrice)
    }

    return maxProfit
}

Bagaimana dengan case tidak ada profit? Kalau harga selalu turun (contoh 2: [7, 6, 4, 3, 1]), maka price - min_price akan selalu negatif. Tapi max_profit diinisialisasi 0, dan max(0, negatif) = 0. Jadi return 0 — sesuai requirement.

Visualisasi

prices = [7, 1, 5, 3, 6, 4]

i=0: price=7  → min_price=7    profit=N/A   max_profit=0
i=1: price=1  → min_price=1    profit=N/A   max_profit=0
i=2: price=5  → min_price=1    profit=4     max_profit=4  ✓
i=3: price=3  → min_price=1    profit=2     max_profit=4
i=4: price=6  → min_price=1    profit=5     max_profit=5  ✓ (new max!)
i=5: price=4  → min_price=1    profit=3     max_profit=5

Return 5

Kompleksitas

Untuk n = 10⁵, solusi ini selesai dalam <1ms di bahasa apapun.

Kenapa Pola Ini Penting

Pola "track minimum dari kiri sambil scan" adalah building block untuk banyak variasi soal:

• Best Time to Buy and Sell Stock II — boleh transaksi berkali-kali
• Best Time to Buy and Sell Stock III — maksimum dua transaksi
• Trapping Rain Water — track max dari kiri dan kanan
• Maximum Subarray (Kadane) — track current_sum dan max_sum

Semuanya berangkat dari ide yang sama: maintain state optimal dari data yang sudah kamu lewati, update state saat kamu maju.

Intisari

Best profit comes from buying at the lowest price seen so far and selling at the current price. Track both in one pass.

Soal ini mengajarkan bahwa brute force bisa runtuh hanya dengan satu observasi sederhana. Selalu tanya sebelum menulis nested loop: "Apa yang sebenarnya perlu saya ingat dari data yang sudah saya lewati?"