Solusi Leetcode - Best Time to Buy and Sell Stock II

Setelah menyelesaikan soal saham dengan satu transaksi, saya penasaran apa yang terjadi kalau saya boleh melakukan banyak transaksi. Kebebasan tambahan ini mengubah cara hitungnya: setiap kenaikan harga dari satu hari ke hari berikutnya bisa menambah total profit.

Batasannya

Input-nya adalah array prices, di mana prices[i] adalah harga saham di hari i. Saya boleh beli dan jual di hari yang sama. Tapi, saya cuma boleh memegang satu saham dalam satu waktu. Tujuannya adalah profit maksimum dari semua transaksi yang valid.

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.

Awalnya saya kira harus mencatat setiap pembelian dan penjualan. Tapi penurunan harga nggak menyumbang apa-apa ke profit. Kita bisa memotong rangkaian kenaikan harga di titik mana pun tanpa mengubah total keuntungannya. Jumlah semua selisih positif memberikan keuntungan itu dan tetap memenuhi batas satu saham dalam satu waktu.

Untuk [7, 1, 5, 3, 6, 4], kenaikannya adalah 1 → 5 dan 3 → 6, jadi total profit-nya 4 + 3 = 7.

Implementasi greedy

Ini implementasi one pass-nya:

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

Awalnya saya kira bakal butuh dynamic programming, tapi pendekatan greedy udah cukup. Algoritma ini berjalan dalam O(n) time dan O(1) space.

Pola yang berguna di sini adalah menjumlahkan setiap keuntungan lokal kalau soalnya membolehkan transaksi tanpa batas yang nggak saling tumpang tindih. Sebelum langsung pakai dynamic programming, cek dulu apakah rangkaian pilihan lokal udah cukup untuk menghasilkan hasil global.