这个题应该是LICS吧

空间上优化了，可是时间上又超了。。总是要用到两重循环。。

啊不好意思看错题了，题目要求这个子序列的数必须是后一项比前一项多1的，比如2,3,4,5,6...还不是一般的LICS

这题我知道了,要分开一步一步来~



看题,切入点是每个元素大小在[1，1000000]之间

首先,原数组里面可能会出现重复的元素,这样在求递增子序列的时候很明显后面出现的会覆盖掉,只保留前面出现的(这点其实非常至关重要)

所以说不用考虑重复元素出现的情况了~

下面的解法我就先分开说,一步一步实现~

1----把第一个子序列的对应元素用大小为1000000数组的进行映射,映射值是该元素所在原数组的下标,重复出现的直接忽略,也就是只保留第一次出现的下标就可以了~没有出现的元素用个标记分开或者初始化全部为不重复标记~

2----用二分法求第二个递增子序列,注意在所求元素的值所对应的第一个子序列里面后一个元素的下标要比前一个大才进行操作(也就是说第一个数组没有出现过的元素可以初始化为最大值表示),二分法求最长公共子序列可以参考

https://bbs.bccn.net/thread-485375-1-1.html

不知道有没有问题,这样看看~

[此贴子已经被作者于2018-6-9 02:39编辑过]