LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Best Time to Buy and Sell Stock

Lacak harga terendah sejauh ini untuk mencari profit terbaik dari satu transaksi saham.

Di artikel ini 3 bagian

Pilih satu hari untuk membeli dan satu hari setelahnya untuk menjual, supaya selisih harga positifnya paling besar. Solusi pertama aku 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. Aku 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.

Baseline ini mengecek setiap pasangan hari beli dan hari jual:

javascript
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

Untuk setiap calon hari jual, aku cuma perlu harga terendah sebelumnya. minPrice menyimpan harga itu, sementara maxProfit menyimpan profit terbaik sejauh ini.

javascript
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:

javascript
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 5
  • 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:

java
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
    }
}

Versi satu pass butuh O(n) waktu dan O(1) extra space. Kalau harga terus turun, minPrice ikut turun dan maxProfit tetap nol.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan