We are given a sequence of n numbers, a1, a2, · · · , an and want to find the longest increasing subsequence (lis); that is, we want to find indices i1 < i2 < · · · < im such that aij < aij+1 and m is as large as possible. for example, given the sequence 5, 2, 8, 6, 3, 6, 9, 7 we have an increasing subsequence 2, 3, 6, 9 and there is no longer increasing subsequence.

1. give a recursive dynamic programming recurrence (just give the function) for the lis of a sequence a1, a2, · · · , an. (hint : let li be the length of the lis in a1, a2, · · · , ai , let ai be index of the smallest possible largest element in that increasing subsequence, and let bi be index of the second-largest element in that increasing subsequence. express li recursively. you may assume a dummy element a0 = −[infinity])

2. give the algorithm iteratively with memoization. analyze the time required and give corresponding pseudocode