In class, we saw how given two strings x = x1x2 ...xn and y = y1y2 ...ym, we can find the longest common substring. For example, if x = 9,2,8,3,7,4,1 and y = 2,3,9,6,8,5,7,1,4 then the longest common substring is 9, 8, 7, 1. However, suppose we want to compute the longest one that is also increasing, which in this case would be 2, 3, 4. Design an algorithm to compute this. (Hint: We also saw in class how to compute the longest increasing subsequence using Dynamic Programming. You need to figure out how to combine the ideas in both algorithms to compute this)

(a) Design the algorithm. (b) Prove your algorithm is correct. (c) Analyze the run time of your algorithm. For full marks, your algorithm should run in polynomial time.