Solusi Leetcode - Best Time to Buy and Sell Stock

Pilih satu hari untuk membeli dan satu hari setelahnya untuk menjual, supaya selisih harga positifnya paling besar. Solusi pertama saya mengecek setiap pasangan, jadinya O(n²). Dengan melacak harga terendah yang udah ditemui sejauh ini, scan-nya bisa turun jadi O(n).

Batasan satu transaksi

Input-nya adalah array prices, dengan prices[i] sebagai harga di hari ke-i. Saya boleh membeli sekali lalu menjual sekali setelahnya, jadi hari jual harus datang setelah hari beli. Harga yang terus turun nggak menghasilkan profit, dan input yang kosong atau cuma satu hari juga mengembalikan nol.

Awalnya saya kepikiran untuk mengecek semua kemungkinan pasangan hari beli dan hari jual:

function maxProfitNaive(prices) {
  let maxProfit = 0;

  for (let i = 0; i < prices.length; i++) {
    for (let j = i + 1; j < prices.length; j++) {
      const profit = prices[j] - prices[i];
      if (profit > maxProfit) {
        maxProfit = profit;
      }
    }
  }

  return maxProfit;
}

Cara pairwise ini benar, tapi running time O(n²)-nya naik dengan cepat seiring bertambahnya jumlah hari.

Satu pass dan invariant-nya

Lalu saya melacak harga minimum yang udah ditemui sejauh ini dan profit terbaik di setiap hari. Harga saat ini adalah calon harga jual, sementara minPrice mewakili harga beli valid terbaik sebelum hari itu.

function maxProfit(prices) {
  let minPrice = Infinity; // Track the lowest price seen so far
  let maxProfit = 0; // Track the maximum profit found

  for (let i = 0; i < prices.length; i++) {
    // If current price is lower, update our minimum
    if (prices[i] < minPrice) {
      minPrice = prices[i];
    }
    // Otherwise, check if selling now gives better profit
    else if (prices[i] - minPrice > maxProfit) {
      maxProfit = prices[i] - minPrice;
    }
  }

  return maxProfit;
}

Setelah hari i, minPrice berisi harga terkecil dari hari 0 sampai i. Nilai maxProfit adalah profit valid terbaik untuk hari-hari tersebut. Kalau harga saat ini lebih rendah, algoritmanya meng-update minPrice untuk penjualan berikutnya. Kalau nggak, prices[i] - minPrice memberikan profit terbaik dari menjual hari ini. Nilai maxProfit menyimpan hasil terbaik dari hari-hari sebelumnya.

Trace, implementasi Java, dan kompleksitas

Untuk [7, 1, 5, 3, 6, 4], state dari one pass ini berubah seperti berikut:

const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5

Trace-nya:

• Hari 0: harga 7, minPrice jadi 7, profit 0
• Hari 1: harga 1, minPrice jadi 1 (lebih rendah!), profit masih 0
• Hari 2: harga 5, minPrice 1, profit = 5 - 1 = 4
• Hari 3: harga 3, minPrice 1, profit = 3 - 1 = 2 (nggak lebih baik)
• Hari 4: harga 6, minPrice 1, profit = 6 - 1 = 5 (lebih baik!)
• Hari 5: harga 4, minPrice 1, profit = 4 - 1 = 3 (nggak lebih baik)

Profit terbaiknya 5, dari membeli di harga 1 dan menjual di harga 6.

Versi Java-nya menjaga invariant yang sama:

public class StockProfit {
    public static int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;

        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minPrice) {
                minPrice = prices[i];
            } else if (prices[i] - minPrice > maxProfit) {
                maxProfit = prices[i] - minPrice;
            }
        }

        return maxProfit;
    }

    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit(prices)); // Output: 5
    }
}

Solusi pairwise pertama saya memang intuitif, tapi informasi yang dilacaknya lebih banyak dari yang dibutuhkan. Versi one pass memakai waktu O(n) dan extra space O(1). Versi ini juga bisa menangani array yang terus menurun, karena maxProfit tetap nol sementara minPrice terus bergerak turun.

Pertanyaan utamanya adalah state apa yang memungkinkan setiap keputusan berikutnya. Di sini, harga minimum dan profit maksimum udah cukup, jadi pencarian pairwise nggak diperlukan.