codes must be in c programming

1. Devise a dynamic programming algorithm that takes a sequence S of n integers a, ..., an as input, and outputs the longest and strictly increasing subsequence. Note that the numbers in the subsequence don't need to be successive. Also, all the inputs given to the algorithm are assumed to be legitimate, i.e. the users are assumed to provide only integers. 2. Devise a dynamic programming algorithm that takes three bit strings X = x1 ... xn Y = y1 ... Ym, and Z = 2 ... Zn+m, and output 'YES' if Z is an interleaving of X and Y, and 'NO' otherwise. Note that the string Z is called an interleaving of X and Y if Z can be obtained by interleaving the bits in X and Y in a way that it maintains the left-to-right order of the bits in X and Y. For example, if X = 101 and Y = 01, then 2 = 10011 is an interleaving of X and Y, but Z2 = 11010 is not. Also, all the inputs given to the algorithm are assumed to be legitimate, i.e. the users are assumed to provide only bit strings