Code must be written in C Language/ UBUNTU environment.

To get full credit for each question, you need to provide a brief explanation of your codes and the efficiency analysis with comments.

1. Devise a dynamic programming algorithm that takes a sequence 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