Maximum Contiguous Subsequence Sum Problem

Maximum Contiguous Subsequence Sum (MCSS) adalah nilai maksimum dari penjumlahan subsequence bilangan bulat (boleh bernilai negative).  
Pada kasus degenerative (semua anggota dari sequence bernilai negative) MCSS = 0 dan subsequence-nya adalah sebuah empty subsequence (contiguous juga).
Maximum Contiguous Subsequence Sum Problem


 Contoh:
Jika diberikan input [-2, 11, -4, 13, -5, 2] maka MCSQ = 20
Jika diberikan input [1, -3, 4, -2, -1, 6] maka MCSQ = 7
Untuk mencari MCSS bisa menggunakan beberapa Algoritma

  1. Metode Brute Force O(N3)

n = length(a);
maks = 0;
for (i = 1 to n){
   for ( j = i to n){
       jumlah = 0;
       for (k = i to j){
           jumlah = jumlah + a(k);
           if (jumlah > maks){
                maks = jumlah ;               
           }  //end if
       }  //end for k
   }  //end for j
}  //end for i
Dari pseudocode tersebut, dapat dilihat nested loops yang ada menghasilkan O(N3).

  1. O(N2) Algorithm
Untuk algoritma 1, akan dibuat lebih efisien lagi dengan cara menghilangkan 1 loop. Hal ini bisa didapat ketika jumlah subsequence i, … , j-1 sudah dihitung, maka untuk mendapatkan jumlah subsequence i,… , j hanya butuh 1 (satu) proses penambahan saja, dimana informasi tersebut pada algoritma 1 langsung dibuang. Dengan cara ini didapatkan pseudocode dengan kompleksitas O(N2).
n = length(a);
maks = 0;
for i = 1:n
   jumlah = 0;
   for j = i:n
       jumlah = jumlah + a(j);        
       if jumlah > maks
           maks = jumlah ;
       end
   end
end
  1. Linear Algorithm O(N)
Untuk meningkatkan efisiensi algoritma 2, yang harus dilakukan adalah menghilangkan inner loop pada algoritma 2. Hal ini bisa dilakukan dengan mengeliminasi subsequences yang tidak mempengaruhi nilai maksimal.



Misalkan < 0 dan q > j maka Ai … Aq bukan MCSS..
Dengan kata lain, jika jumlah dari Ai … Aj dihilangkan maka akan didapatkan jumlah Aj+1 … Aq yang lebih besar dari pada jumlah Ai … Aq.
Jadi, jika didapatkan jumlah sequences < 0 maka inner loop akan melakukan break out.
Langkah yang harus diterapkan adalah
  • Hitung jumlah dari i = 0
  • Ketika terdapat nilai baru, jadikan MCSS
  • Jika penjumlahan yang didapat < 0 saat j, maka lakukan penjumlahan baru mulai dari j+1
n = length(a);
maks = 0;
jumlah = 0;
for j = 1:n
   jumlah = jumlah + a(j);
   if jumlah > maks
       maks = jumlah ;
   elseif jumlah < 0
       jumlah = 0;
   end
end

Uji Coba
Ketiga algoritma tersebut kemudian dijalankan di Matlab R2010a untuk membandingkan time complexity apakah sesuai dengan teori. Untuk array yang akan diolah, dilakukan proses pengambilan acak sebanyak n antara bilangan -100 s/d 100 dengan menggunakan distribusi uniform diskrit dan angka yang diambil boleh berulang. Masing-masing algoritma dilakukan sebanyak 1000 kali untuk tiap n yang sama kemudian dihitung rata-rata dari waktu yang didapat sehingga didapat hasil sebagai beriku.
n
O(n3)
O(n2)
O(n)
10
0.305x10-4
0.078 x10-4
0.035 x10-4
102
44 x10-4
1.2 x10-4
0.075 x10-4
103
2.56
7.5 x10-3
0.3 x10-4
104
N/A
0.868
3 x10-4
 

Untuk nilai N/A maksudnya adalah belum didapat karena program berjalan > 12 jam tetapi belum berhenti dan langsung di stop saat masih running.

Grafik Kompleksitas Maximum Contiguous Subsequence Sum Problem

Kesimpulan
Algoritma 1 memerlukan waktu yang lama dibandingkan yang lainnya sehingga perlu diberikan efisiensi dengan memperhatikan correctness. Dengan Algoritma yang efisien kita bisa membuat running time yang lebih singkat.
Daftar Pustaka


Komentar

Posting Komentar