题目链接：300

解题思路

这道题使用传统的dp来思考，即 dp[i] 表示 包含nums[i]的最长递增子串的长度，时间复杂度是O(n²)。

考虑换一个思路，创建一个新的数组tails[]。tails[i] 表示 长度为i+1的递增子序列中最小的结尾值。例如 [4,2,3,5]，tails[1] == 3，因为长度为1+1=2的递增子序列有[4,5], [2,3], [2,5], [3,5]，而其中最小的结尾值是[2,3]中的 3。该题的答案即为 len(tails)。

之所以维护一个tail[]数组，是因为这样可以使用binary search减少查找的时间复杂度。

在传统的dp定义中，对于任意一个元素num[i]，都需要遍历它前面的每一个元素，以此来判断自己接在哪个数后面的收益更大，而之所以需要遍历，是因为前面的元素是无序的。

如果我们维护一个 tails[] 数组，从它的定义即可知，这是一个严格单调递增的数组（tails[i] 相比于 tails[i-1] 拥有更长的子序列，自然结尾的值也更大）。因此对于任意 nums[i]，可以使用 binary search 在 tails[] 数组中找到比它小的值中最大的那个值（即 biggest smaller value），将自己接在它后面从而形成长度 +1 的新递增子序列，同时需要更新 tails[]数组。

func lengthOfLIS(nums []int) int {
    // tails[i]: the tail number of increasing subsequence with length (i + 1)
    tails := make([]int, 0, len(nums))
    tails = append(tails, nums[0])

    for i := 1; i < len(nums); i++ {
        tailsIndex := binarySearchBiggestSmaller(tails, nums[i])
        if tailsIndex == -1 {
            // no smaller num before
            tails[0] = min(tails[0], nums[i])
        } else if tailsIndex == len(tails) - 1 {
            // the largest num is smaller than cur
            tails = append(tails, nums[i])
        } else {
            // update tails[]
            tails[tailsIndex + 1] = min(tails[tailsIndex + 1], nums[i])
        }
    }

    return len(tails)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

// return index
func binarySearchBiggestSmaller(array []int, pivot int) int {
    left := 0
    right := len(array) - 1
    for left < right - 1 {
        mid := left + (right - left) / 2
        if array[mid] >= pivot {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if array[right] < pivot {
        return right
    }
    if array[left] < pivot {
        return left
    }
    return -1
}

时间复杂度：O(nlogn)
空间复杂度：O(n)