最长递增子序列
最长递增子序列
时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M 热度指数：7903
本题知识点： 二分 动态规划
题目描述
给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
示例1 输入
[2,1,5,3,6,4,8,9,7]
输出
[1,3,4,8,9]
示例2
输入
[1,2,8,6,4]
输出
[1,2,4]
说明
其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
备注:
Time Exceeded Try
2020-10-12
牛客网的热门题目，做了leetcode的第300题才知道解法。不过解法依然是O(n^2)的复杂度，没有用上二分法，因此依然是超时了。
直接从正面出发，两个循环解决问题，并没有那么复杂。 本来认为暴力法复杂度都到2^n去了，但其实只要考虑选择当前元素的时候，能够接上前面最长的子元素序列即可，而后面的元素不一定选择当前元素。因此每次选择元素的时候，都把前面可以选择的子序列遍历一遍，由于使用cache，其实一轮遍历也只是O(i)而已，两轮下来就是O(n^2)。
为了不用最后把全员遍历一遍，实现把最大的float('inf')无限大元素插入到末尾，最终不管那个子序列肯定是要选择这个元素的，因此用最后这个元素的子序列来获取答案即可。
相比leetcode300，这里面一是要求求解出子序列而不是只要求长度，二是求解出最长子序列后还要考虑排序最小的子序列，三是要求用O(nlgn)的解法，所以其实整体难度高了不少。
不过时间复杂度上先不管了，至少能得到正确子序列了，复杂度差别也不是那么大。
class Solution:
def LIS(self , arr ):
arr.append(float('inf'))
cache = [[arr[i]] for i in range(len(arr))]
for i in range(len(arr)):
for j in range(0, i):
if arr[j] < arr[i] and len(cache[j]) + 1 > len(cache[i]):
cache[i] = cache[j] + [arr[i]]
elif arr[j] < arr[i] and len(cache[j]) + 1 == len(cache[i]):
# 字典序比较，小于当前子序列的可自行替代，
# 并不影响最后总长度，因为不管前面是哪个，该子序列后面都是arr[i]
if cache[j] < cache[i]:
cache[i] = cache[j] + [arr[i]]
return cache[-1][:-1]
Failed Try
2020-10-09
求解出了长度，但不知道怎么恢复出最长子序列来。
不过问题还在于动态规划的思路出现了错误，导致求解个长度也非常的繁琐。这里是选择了第idx元素之后，后面的数列能够拥有的最长长度，导致求解出总长度后还要减去当前idx元素的长度，并且还要考虑如果不选择idx元素，前一个元素idx - 1又是什么情况。 写得非常变扭，虽然最后还是把长度正确求取出来了。
还是要参考leetcode300的解法，也就是这里time exceeded的解法从正面突破。
#
# retrun the longest increasing subsequence
# @param arr int整型一维数组 the array
# @return int整型一维数组
#
class Solution:
def LIS(self , arr ):
# write code here
# backtrack + cache?
# if select current idx, later longest len is cache[cidx]
# if no select current idx, later longest depends on previous valid value
cache = [""] * (len(arr) + 1) # maximum length after select arr[i]
dist = [""] * (len(arr) + 1)
rv = []
def backtrack(arr, selected, preidx, cidx):
if cidx == len(arr):
return len(selected)
if len(selected) and arr[cidx] < selected[-1]:
return backtrack(arr, selected, preidx, cidx + 1)
else:
currlen = len(selected)
if cache[cidx + 1] == "":
# select current
selected.append(arr[cidx])
total_len = backtrack(arr, selected, cidx, cidx + 1)
cache[cidx] = total_len - currlen
selected.pop()
else:
total_len = currlen + cache[cidx]
# not select current
total_len_not = backtrack(arr, selected, preidx, cidx + 1)
cache[preidx + 1] = max(cache[cidx + 1], total_len_not - currlen)
return max(total_len, total_len_not)
backtrack(arr, [], 0, 1)
print(str(cache[0]))