You are given a sequence of numbers in an array A = [0, 8, 2, 12, 4, 10, 6, 14,

Question

You are given a sequence of numbers in an array A = [0, 8, 2, 12, 4, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]. Let L = L[1], ..., L[16] be an array of size 16 such that L[i] stores the length of the longest increasing subsequence of A that ends with A[i]. Solve the following:

Fill the entries of L below. (Use Length-LIS algorithm)

Length-LIS(A, n)

- For i = 1 to n {

- max ? 1

- For j = 1 to (i ? 1) {

- If (A[j] < A[i]) {

- If (max < L[j] + 1) max ? L[j] + 1

}

- L[i] ? max

}

}

- return the maximum of L[i]’s

Explanation / Answer

L = [1, 2, 2, 3, 2, 3, 3, 4, 2, 4, 3, 5, 3, 5, 4, 6]

LOngest increasing subsequence:
0, 2, 6, 9, 11, 15

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.