[Leetcode] Longest Increasing Subsequence

Problem

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Analysis

• 遍历所有的数字，同时维护一个valid数组，来保存当前扫描到的有用的数
• tail 表示当前valid数组的最后一个数， 
• 对于当前读到的数x
• 如果x>tail，则把x append到数组中
• 如果x<valid数组的第一个数，则将其替换为x
• 否则，则二分查找到valid数组中第一个大于或等于x的数，替换为x
• 返回valid数组中有效的数个数

时间复杂度: O(nlogn)

Code

Reference
[1] http://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/
[2] https://leetcode.com/problems/longest-increasing-subsequence/