Question 4. (25 points) Let S=x1x2xn be a sequence of n distinct items. For every i, 1in, let (i) denote the length of a longest increasing subsequence that ends with xi. For example, if S=fewvbazxcthenthe9 values of (i) are: 1,1,2,2,1,1,3,3,2 The length of a longest increasing subsequence, denoted by LIS, is obviously equal to the largest of the (i) values, i.e., LIS=max1in(i) Let the set k,1kLIS, be the subsequence of S containing all the xi whose (i) equals k. In the above example, for which LIS=3 and the 9 values of (i) are 1,1,2,2,1,1,3,3,2, we have: 1=x1x2x5x6=feba(hence1=4)2=x3x4x9=wvc(hence2=3)3=x7x8=zx(hence3=2) 1. (10 points) Prove that every k subsequence is decreasing 2. (15 points) Prove that max{1,2,,LIS}n/LIS. Question 4. (25 points) Let S=x1x2xn be a sequence of n distinct items. For every i, 1in, let (i) denote the length of a longest increasing subsequence that ends with xi. For example, if S=fewvbazxcthenthe9 values of (i) are: 1,1,2,2,1,1,3,3,2 The length of a longest increasing subsequence, denoted by LIS, is obviously equal to the largest of the (i) values, i.e., LIS=max1in(i) Let the set k,1kLIS, be the subsequence of S containing all the xi whose (i) equals k. In the above example, for which LIS=3 and the 9 values of (i) are 1,1,2,2,1,1,3,3,2, we have: 1=x1x2x5x6=feba(hence1=4)2=x3x4x9=wvc(hence2=3)3=x7x8=zx(hence3=2) 1. (10 points) Prove that every k subsequence is decreasing 2. (15 points) Prove that max{1,2,,LIS}n/LIS