最长递增子序列白话文解释

非原创，百度一波总结下来的：


一共需要两个辅助数组和一个辅助变量：
dp数组：用来存储位置i对应的最长子序列的长度
end数组：用来存储长度为i的子序列的最后一个元素的最小值
len：用来记录当前找到的最长子序列的长度

举个例子
[3,2,5,8,6,7]
end数组：
i=0: 3	长度为1的子序列为：3
		end=[3]
i=1:2<3 长度为1的子序列为：2(用2替换3,因为这是是最容易使子序列扩展为长度为2的子序列的值)
		 end=[2]
i=2:5>2	所以长度为1的子序列可以扩展成一个长度为2的子序列
		长度为1的子序列为：2
		长度为2的子序列为：2 5
		end=[2 5]
i=3:8>5 所以长度为2的子序列可以扩展成一个长度为3的子序列
		长度为1的子序列为：2
		长度为2的子序列为：2 5
		长度为3的子序列为：2 5 8
		end=[2 5 8]
i=4:6>5&&6<8 所以长度为2的子序列可以扩展成一个长度为3的子序列
		长度为1的子序列为：2
		长度为2的子序列为：2 5
		长度为3的子序列为：2 5 6(用6替换8,因为只是最容易使子序列扩展为长度为4的子序列的值)
		end=[2 5 6]
i=5:7>6 所以长度为3的子序列可以扩展成一个长度为4的子序列
		长度为1的子序列为：2
		长度为2的子序列为：2 5
		长度为3的子序列为：2 5 6
		长度为4的子序列为：2 5 6 7	
		end=[2 5 6 7]
笔记：我们用end[i]来存储长度为i+1的子序列的最后一个元素的最小值，因为这是最有希望使子序列扩展的值
当a[x]>end[i]时，那么长度为i+1的子序列必定可以扩展成一个i+2的子序列，如果(old=end[i+1])>a[x]，那么就令
end[i+1]=a[x]，他的含义是只要a[y]>a[x]即使a[y]<old，那么长度为i+2的子序列也必然可以扩展为一个长度为i+3的子序列。
所有最终结束时end数组为[2,5,6,7]即end[i]表示长度为(i+1)的子序列的最后一个元素值。


遍历结束后也会生成    dp数组：
arr:[3,2,5,8,6,7]
dp :[1 1 2 3 3 4]
len=4
dp[i]表示到arr[i]为止最长的递增子序列，得到字典序最小的元素只需要倒过来遍历dp，依次输出最先遇到的长度为len,len-1,len-2....1的arr元素即可。
res用来存储字典序最小的最长子序列。
即：    len=4  dp[5]==4 ==>res[3]=arr[5]=7
	len=3  dp[4]==3 ==>res[3]=arr[4]=6
		 dp[3]==3  pass因为需要的是字典序最小的
    	len=2  dp[2]==2 ==>res[3]=arr[2]=5
	len=1  dp[1]==1 ==>res[3]=arr[1]=2
		 dp[0]==1  pass因为需要的是字典序最小的
	结果：res=[2,5,6,7]
笔记：设dp[x]==dp[y]&&x<y那么a[x]必定大于a[y]，因为如果a[x]<a[y]，那么dp[x]对应的子序列必定可以扩展为长度dp[x]+1的子序列即dp[y]=dp[x]+1>dp[x]，矛盾，所以a[y]<a[x]