• or if Zi > Zi+1 it must be th
In class we showed how to calculate the longest increasing subsequence. This requirement turned out too
strict and we are interested to finding the longest close-to-increasing subsequence.
We say that a sequence of numbers Z is close-to-increasing if the size of any decreasing substring is at
most 2. So given two consecutive elements in the sequence Zi and Zi+1 it must either be that
• Zi < Zi+1
• or if Zi > Zi+1 it must be that Zi+1 < Zi+2.
Below are some examples of of close-to-increasing sequences:
A = 11 10 18 17 25 33 30 34 27 29
B = 8 99 33 34 40 11 13 20 23 22
As we can see A2 = 10 < 11 = A1 but A3 = 12 > 10 = A2 so the constraint is satisfied. Same is true in
other places where monotonicity fails at A7, A11, A14. Similar for sequence B.
The following are examples of sequences that are not close-to-increasing:
C = 10 11 13 12 18 30 27 22 33 40 44
D = 17 16 1 11 13 12 15 19 30 25 33
We have C6 = 30 > 27 = C7 and C6 = 27 > 22 = C9 so the constraint is violated. Similarly D1 > D2 > D3 so
the sequence D is not close-to-increasing. For example if X = D the longest close-to-increasing subsequence
is Z = 17, 1, 11, 13, 12, 15, 19, 30, 25, 33 for a size of 11. You may assume all numbers in X are unique.
a. (25 points) Give a dynamic programming
LCIS+(i, j) : is the longest closed to increasing subsequence that ends and XiXj , i.e., its last element
is Xj and its second to last element is Xi
. Give a recursive formula, prove its correctness and write a
bottom-up implementation.
b. (15 points) Give a dynamic programming algorithm using the following optimal subproblem structure
LCIS+(i) is the longest closed to increasing subsequence that ends and Xi and the auxiliary optimal
subproblem structure LCIS+,inc(i) is the longest closed to increasing subsequence that ends at Xi
in
an increasing fashion (the second to last element is smaller than Xi). Give a recursive formula for both
optimal subproblem structures, prove their correctness and write a bottom-up implementation.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
