CMI2017-B-6

Question

We are given a sequence of pairs of integers $(a_1, b_1),(a_2, b_2), \dots ,(a_n, b_n)$. We would like to compute the largest $k$ such that there is a sequence of numbers $c_{i_1} \leq c_{i_2} \leq \dots \leq c_{i_k}$ with $1 \leq i_1 < i_2 < \dots < i_k \leq n$ and for each $j \leq k$, $c_{i_j}=a_{i_j}$ or $c_{i_j} = b_{i_j}$ . Describe an algorithm to solve this problem and explain its complexity.

Answer 1

This is essentially a variant of the longest increasing (or non-decreasing) subsequence problem. Here instead of a single array, we have the choice from two of them a[i] or b[i].

We will maintain two states for each i, dp[i][j] where 1 <= i <= n and j = {0, 1}.

Intuitively, dp[i][0] denotes the length of the longest subsequence when a[i] is present in the subsequence

Similarly, dp[i][1] denotes the length of the longest subsequence when b[i] is present in the subsequence
 

dp[i][0] = 1 + MAX { dp[k][0]                  if a[i] >= a[k]  for all 1 <= k < i

                                dp[k][1]                  if a[i] >= b[k]  for all 1 <= k < i

                                0                            Otherwise }
 

dp[i][1] = 1 + MAX { dp[k][0]                        if b[i] >= a[k]  for all 1 <= k < i

                                   dp[k][1]                        if b[i] >= b[k]  for all 1 <= k < i

                                   0                                    Otherwise }

Answer will be the maximum over all dp[x][y] entries (1 <= x <= n and y = {0, 1})

Complexity Analysis:

Space: Ɵ(2*n) = Ɵ(n)
Time: Ɵ(n*n) = Ɵ(n²), Sum(2*(i-1)) for all 1 <= i <= n

Trivial exercise:
How to find out the maximum subsequence (not just the length)? What if more than one are of the maximum length?

Answer 2