LeetCode Grinding
Algorithms2 menit baca

Solusi Leetcode - Best Time to Buy and Sell Stock II

Jumlahkan setiap kenaikan harga untuk mendapatkan profit maksimum dari transaksi saham yang jumlahnya tanpa batas.

Di artikel ini 3 bagian

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

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

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

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan