最长递增子序列问题
合并LIS（JLIS）第k个最大递增子序列（KLIS）对于求单个序列的最长递增子序列网上的太多就不多写了，以下是它的一些进阶算法
合并LIS（JLIS）
题意
两个整数序列A和B各自得到长度为0以上的递增子序列后，合并成升序的序列，那么，暂且把这种序列称为合并递增子序列。这些序列中长度最长的序列就是合并最长递增子序列。(JLIS. Joined Longest Increasing Subsequence)。例如，“13479”是“149”和“347”的合并LIS，因为合并“19”和“347”就能得到“13479”。
代码：
const long long NEGINF = -9876543210int n,m,A[100],B[100];int catce[101][101];int jlis(int indexA,int indexB){//记忆化搜索int &ret = cache[indexA+1][indexB+1];if(ret != -1)return ret;//A[indexA]、B[indexB] 已存在，所以至少有两个元素ret = 2; // 因为这两个一定有大小之分long long a = (indexA == -1? NEGINF: A[indexA]);long long b = (indexB == -1? NEGINF : B[indexB]);long long maxElement = max(a,b); //选最大的再进行增长//找出下一个元素for(int nextA = indexA+1;nextA<n;++nextA)if(maxElement < A[nextA])ret = max(ret,jlis(nextA,indexB)+1);for(int nextB = indexB+1;indexB<m;++nextB)if(maxElement<B[nextB])ret = max(ret,jlis(indexA,nextB)+1);return ret;}
第k个最大递增子序列（KLIS）
题目
某个整数序列中，去掉0个以上的数字后，剩余的部分就是原序列的子序列。例如，{7,4,9}、{10,4}、{10,9}等是{10,7,4,9}的子序列。而序列{10, 4, 7}具有不同于原序列的排列顺序，因而不属于{10,7,4,9}的子序列。严格递增的子序列称为递增子序列。序列的递增子序列中，最长的序列称为最大递增子序列（LIS）。例如：{5,20,21,22,8,9,10}的最大递增子序列是{5,8,9,10}。（不唯一）
给出以不同数字组成（无重复数字）的序列时，请编写程序，计算此序列的LIS中按照字典序排在第k个位置的LIS。
输入
第一行输入测试用例的个数C（C<=50）。各测试用例的第一行输入序列中元素的个数n（1<=n<=500）和k（1<=k<=2*109）。第二行输入序列的n个元素。各元素是大于等于1而小于等于100,000的整数，且同一数字只出现1次。
可以假设序列的LIS至少有k个。
输出
每个测试用例在第一行输出LIS的长度l，第二行以l个整数输出第k个LIS。
示例输入：
3
8 6
5 1 6 4 3 2 8 7
8 4
2 1 4 3 6 5 8 7
8 2
5 6 7 8 1 2 3 4
示例输出：
3
1 4 8
4
1 3 6 8
4
5 6 7 8
