Longest Continuous Subsequence

应用

题型

• 找连续最长上升子序列，比如1,2,3,4,5,6
• 找连续最长相同子序列，比如aaabbbdddddd
• range summary问题，比如合并range/interval，或者找interval的补集。这种问题的核心是对一个sorted array进行traversal。如果题目已经给我们一个unsorted array，我们可以先去sort一下，比如range summary and missing range问题。如果题目没有给我们存储数据的data structure，那我们自己要去用BST maintain一个sorted array。

题目

range summary类型

• Leetcode 352. Data Stream as Disjoint Intervals

找连续最长相同子序列

• Leetcode 28. Implement strStr()
• Leetcode 38. Count and Say
• Leetcode 89. Gray Code (这道题虽然不是LCS问题，但是和count and say非常类似，都是滚动数组。这里我们要找规律)
• Leetcode 58. Length of Last Word