题解 | #最长递增子序列#
最长递增子序列
http://www.nowcoder.com/practice/9cf027bf54714ad889d4f30ff0ae5481
python使用bisect和patient sort, 借助pre记录每个位置的前驱
import bisect class Solution: def LIS(self , arr ): stack = [0] pre = [-1] * len(arr) class Range: def __getitem__(self, i): return arr[stack[i]] def __len__(self): return len(stack) for i in range(1, len(arr)): idx = bisect.bisect_left(Range(), arr[i]) if idx < len(stack): stack[idx] = i pre[i] = stack[idx - 1] if idx - 1 >=0 else -1 else: pre[i] = stack[-1] stack.append(i) cur = stack[-1] res = [] while cur != -1: res.append(arr[cur]) cur = pre[cur] return res[::-1]