-
Diberikan potongan program berikut ini:
program hahaha; var n, i, j, hehe : integer; a, hoho : array [0..1000] of integer; begin read(n); for i := 1 to n do read(a[i]); for i := 1 to n do hoho[i] := 1; for i := 1 to n do for j := 1 to i-1 do if (a[j] < a[i]) and (hoho[j] + 1 > hoho[i]) then hoho[i] := hoho[j] + 1; hehe := 0; for i := 1 to n do if (hoho[i] > hehe) then hehe := hoho[i]; write(hehe); end.Berapakah nilai keluaran dari program tersebut, jika diberi masukan sebagai berikut?10 4 1 6 2 8 3 0 7 9 5
Nilai hoho[i] akan terus berubah jika terdapat nilai hoho[j] yang sama dengan a[j] < a[i].
Sehingga jika awal semua nilai hoho = i maka:
hoho = (1,1,1,1,1,1,1,1,1,1)
i = 1, hoho = (1,1,1,1,1,1,1,1,1,1)
i = 2, hoho = (1,1,1,1,1,1,1,1,1,1)
i = 3, hoho = (1,1,2,1,1,1,1,1,1,1)
i = 4, hoho = (1,1,2,2,1,1,1,1,1,1) karena hoho[4] = 2 dan terdapat nilai
yang lebih kecil, yaitu 1.
i = 5, hoho = (1,1,2,2,3,1,1,1,1,1) a[5] lebih besar dari a[3], dan hoho[3]
bernilai 2.
i = 6, hoho = (1,1,2,2,3,3,1,1,1,1) karena nilai a yang lebih kecil dengan hoho
terbesar adalah index 4, maka nilai hoho[6] menjadi hoho[4] + 1
i = 7, hoho = (1,1,2,2,3,3,1,1,1,1)
i = 8, hoho = (1,1,2,2,3,3,1,4,1,1) nilai a yang lebih kecil dari 7 dengan nilai
hoho terbesar adalah index 6, yaitu a[6] = 3 dengan nilai hoho[6] = 3, maka hoho[8] = hoho[6] + 1 = 4
i = 9, hoho = (1,1,2,2,3,3,1,4,5,1)
i = 9, hoho = (1,1,2,2,3,3,1,4,5,4)
Setelah menemukan semua nilai hoho, selanjutnya hehe akan menyimpan nilai hoho terbesar karena terus mengganti nilai setiap terdapat yang lebih besar di hoho[i]. Dengan demikian keluaran program tersebut adalah 5.
Potongan program tersebut adalah untuk mencari longest increasing subsequence.