Pengaplikasian Dynamic Programming untuk Masalah Maximum Sum Subrectangle pada Array 2-Dimensi

Abstract

Dynamic programming adalah salah satu algoritma yang digunakan untuk mengoptimalisasi nilai dari suatu permasalahan yang sangat kompleks dengan memecah permasalahan tersebut menjadi bagian-bagian dari sebuah permasalahan. Pada dasarnya, dalam algoritma dynamic programming, pemecahan suatu masalah dapat dibagi menjadi beberapa tahapan sehingga jalan keluar/solusi dari sebuah persoalan yang ada dapat dipandang sebagai hasil optimum yang dapat dijadikan keputusan yang saling berkaitan dengan mengacu pada rangkaian keputusan. Rangkaian keputusan berguna untuk mencoba semua kemungkinan-kemungkinan dari rangkaian-rangkaian keputusan. Rangkaian keputusan yang telah dihasilkan memberikan solusi total yang optimum. Rangkaian tersebut berisikan sub-sub rangkaian optimum atau tidak dapat optimum jika konsep berpengaruh pada proses perhitungan angka sehingga tidak akan menghasilkan hasil yang optimum. Penerapan metode dynamic programming ini amat penting dalam bidang matematika untuk menghitung nilai maximum sum subrectangle. Permasalahan maximum sum dari subrectangle pada array 2-dimensi adalah permasalahan umum yang sering terjadi. Untuk menyelesaikan masalah tersebut dapat digunakan dengan metode dynamic programming. Dengan menggunakan metode dynamic programming, hasil dari perhitungan maksimumnya akan menjadi lebih optimum. Makalah ini akan membahas mengenai penggunaan algoritma dynamic programming dengan menggunakan algoritma Kadane pada penerapannya dalam pembelajaran matematika dengan contoh penggunaannya sebagai fungsi pengoptimalisasi dari algoritma Kadane sehingga memiliki hasil kompleksitas O(N^3)