Pemrograman DinamisMenengahFase D–FE1E5

Kadane (Max Subarray)

Algoritma Kadane mencari deret bagian (subarray) berurutan dengan jumlah terbesar, hanya dalam satu kali telusur. Idenya sederhana: di tiap langkah, pilih memperpanjang deret sebelumnya atau memulai deret baru dari titik ini — mana yang lebih menguntungkan. Dengan begitu jumlah terbaik ditemukan tanpa mengecek semua kemungkinan. Visualisasi menjalankan dompet berjalan dan menyorot jendela paling untung.

Contoh kasus

Mencari rentang hari beli dan jual yang memberi keuntungan maksimal dari sederet naik-turun harga harian.

Silabus

Di tiap langkah, perpanjang deret atau mulai baru — mana yang lebih untung; lacak nilai terbaik.

Tujuan Belajar

·Memahami ide dasar pemrograman dinamis
·Menjelaskan pilihan lanjut atau mulai ulang di tiap langkah
·Menemukan subarray berjumlah maksimum dalam satu telusur

Cara Kerja

·Jalankan dompet berjalan mulai dari 0.
·Di tiap elemen, dompet menjadi nilai maksimum antara elemen itu sendiri dan dompet ditambah elemen.
·Bila dompet menjadi negatif, buang dan mulai deret baru.
·Catat nilai dompet terbesar yang pernah dicapai sebagai jawaban.

Prasyarat

·Array dan perulangan
·Konsep menyimpan nilai terbaik sementara

Contoh Nyata

·Analisis rentang untung dan rugi harga saham.
·Deteksi segmen sinyal terkuat.
·Pengolahan citra dan analisis genom.

Kompleksitas O(n)