Kalau cuma boleh satu transaksi saham, aku perlu mencari hari beli terbaik dan hari jual setelahnya. Kalau jumlah transaksinya bebas, setiap kenaikan harga antar hari bisa diambil.
Batasannya
Input berupa array prices, dengan prices[i] sebagai harga saham pada hari i. Beli dan jual pada hari yang sama boleh, tapi aku cuma bisa memegang satu saham dalam satu waktu. Tujuannya mencari total profit maksimum.
Kalau harga naik beberapa hari berturut-turut, menjual lalu membeli lagi di harga yang sama bikin total profit-nya tetap sama. Misalnya, ambil keuntungan dari hari 1 ke hari 2, lalu dari hari 2 ke hari 3. Jumlah keduanya sama dengan keuntungan dari hari 1 ke hari 3. Jadi, algoritmanya cuma butuh selisih positif antara harga yang bersebelahan.
Penurunan harga nggak menambah profit. Memecah rangkaian harga yang naik menjadi beberapa transaksi tetap menghasilkan keuntungan yang sama tanpa memegang lebih dari satu saham.
Untuk [7, 1, 5, 3, 6, 4], kenaikannya adalah 1 → 5 dan 3 → 6, jadi total profit-nya 4 + 3 = 7.
Implementasi greedy
function maxProfit(prices) {
let maxProfit = 0;
// Check each day compared to the previous day
for (let i = 1; i < prices.length; i++) {
// If price increased, add that profit
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
// Example usage:
const prices = [7, 1, 5, 3, 6, 4];
console.log(maxProfit(prices)); // Output: 7
Untuk contoh yang sama, perubahan harga antar hari yang bersebelahan adalah:
- Hari 0 ke Hari 1: 7 → 1 (turun, nggak ada profit)
- Hari 1 ke Hari 2: 1 → 5 (naik! profit = 4)
- Hari 2 ke Hari 3: 5 → 3 (turun, nggak ada profit)
- Hari 3 ke Hari 4: 3 → 6 (naik! profit = 3)
- Hari 4 ke Hari 5: 6 → 4 (turun, nggak ada profit)
Total profit-nya 4 + 3 = 7.
Setiap selisih positif antar hari yang bersebelahan pasti termasuk dalam suatu rangkaian kenaikan. Menjumlahkan selisih dalam satu rangkaian sama aja dengan membeli di harga pertamanya dan menjual di harga terakhirnya. Selisih negatif nggak bisa memperbaiki hasil, jadi aman untuk dilewati. Dengan begitu, scan ini menghasilkan profit maksimum dalam satu kali jalan.
public class StockProfit {
public static int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
maxProfit += prices[i] - prices[i - 1];
}
}
return maxProfit;
}
public static void main(String[] args) {
int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(maxProfit(prices)); // Output: 7
}
}
Kompleksitas dan pola yang bisa dipakai ulang
Scan ini butuh O(n) waktu dan O(1) extra space. Yang perlu disimpan cuma harga sebelumnya dan profit yang terkumpul.
Cara ini berlaku karena jumlah transaksi bebas, tanpa biaya transaksi atau cooldown. Batasan itu bakal mengubah kenaikan harga mana yang bisa diambil.

Memuat komentar...