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:
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.
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
- 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
}
}
Versi satu pass butuh O(n) waktu dan O(1) extra space. Kalau harga terus turun, minPrice ikut turun dan maxProfit tetap nol.

Memuat komentar...