Dynamic ProgrammingMenengahFase D–FE1E5

Kadane's Algorithm

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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

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

Prerequisites

·Array dan perulangan
·Konsep menyimpan nilai terbaik sementara

Real-World Uses

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

Complexity O(n)