A subsequence is an array derived from another array by removing

some or no elements, while keeping the order of the remaining elements

the same.

For instance, let A $=[1,2,6,4,3,2]$

Then $[2,6,3]$ is a subsequence of A$,$ since A $=[1,2,6,4,3,2]$

But $[2,4,6]$ is not a subsequence of A since it cannot be obtained by

removing elements from A$.$

A consecutive subsequence of some array A$,$ is a subsequence of A

of form $[$x$,$ x $+1,$ x $+2,...]$ for some x$.$ For instance, $[1]$ and $[1,2,3]$ are

consecutive subsequences of A but $[1,2,4]$ is not because $4$ is not the

next natural number after $2.$

Given an integer array A of size N with A$[$i$]$ in $[1,$ N $],$ design a dynamic

programming algorithm to find out the maximum length of consecutive

subsequence of A$.$ Notice that A might contain duplicated number, e$.$g$.$

A $=[1,3,1].$

a$)$ Define $($in plain English$)$ sub$-$problems to be solved.

b$)$ Write a recurrence relation for the sub$-$problems.

c$)$ Using the recurrence formula in part b$,$ write an iterative pseudo$-$

code to find the solution. Make sure you specify base cases.

d$)$ What is the complexity of your solution?