Advertisements

Algoritma MCSS (Maximum Contiguous Subsequence Sum)

18 May

Algoritma MCSS (Maximum Contiguous Subsequence Sum) adalah algoritma yang digunakan untuk mencari hasil penjumlahan terbesar dari subsequence (bagian sebuah urutan angka). Jika urutan tersebut berisi bilangan negatif seluruhnya maka MCSS adalah 0.

Masukan yang dibutuhkan untuk algoritma tersebut adalah sembarang bilangan real dengan syarat memiliki tipe data yang sama sehingga dapat dioperasikan dan dibandingkan.

Apakah keluaran yang dihasilkan algoritma MCSS dan tuliskan syarat khusus
yang pasti dipenuhi (jika ada) untuk keluarannya?

Keluaran yang dihasilkan adalah sebuah bilangan yang merupakan jumlah terbesar dari bagian sebuah urutan angka dengan syarat jika urutan tersebut berisi bilangan negatif seluruhnya maka MCSS adalah 0.

Jika diberikan masukan secara berurut 1, -3, 4, -2, -1, lalu 6, apakah keluarannya dan mengapa demikian?

MCSS-nya adalah 7, karena setelah kita membandingkan jumlah setiap subsequence didapat hasil MCSS-nya 7. Selain itu jika kita menggunakan salah satu algoritma MCSS juga akan didapatkan hasil 7.

Apakah harus selalu bilangan-bilangan bulat yang menjadi masukan untuk algoritma MCSS?

Tidak harus. Masukan untuk algoritma tersebut bisa sembarang bilangan real asalkan memiliki tipe data yang sama sehingga dapat dioperasikan dan dibandingkan. Contohnya masukan bertipe Double , Float, dan Long.

Mungkinkah algoritma MCSS menghasilkan bilangan negatif dan mengapamungkin/tidak mungkin?

Tidak mungkin, karena MCSS akan memilih empty sequence (yaitu 0) yang nilainya lebih besar daripada memilih salah satu angka dari urutan tersebut (bilangan negatif) sebagai hasil MCSS.

Jika keluaran yang dihasilkan algoritma MCSS adalah 0, masukan seperti apakah yang membuatnya seperti itu?

Masukan yang mungkin adalah jika seluruh urutan berisi bilangan negatif atau memang setelah dilakukan perhitungan didapat hasil MCSS adalah 0, karena jumlah nilai positif sama dengan jumlah nilai negatif yang saling meniadakan.

mcss brute force mcss quadratic mcss recursive mcss1 recursive mcss2 linear mcss linear mcss 2

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: