最长递增序列

最长递增子序列（Longest Increasing Subsequence, LIS）是指在一个给定的序列中，找到一个严格递增的子序列，并且这个子序列的长度是所有可能子序列中的最大值。

例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，其最长递增子序列可以是 [2, 3, 7, 101]，长度为 4。

下面给出了两种常见的LIS算法实现：

1. MaxIncrSeq：复杂度较高，采用模拟所有可能递增序列的方法，空间耗费较大，仅用于理解LIS结构。
2. MaxIncrSeqSize：优化空间和时间复杂度的实现，通过”贪心+二分查找”的方法快速找到LIS的长度（代码略有简化版未用二分查找，便于直观理解）。

通常面试和竞赛更推荐第二种优化方法，可以将复杂度降为 O(n log n)。

以下是两种实现的Go语言代码。

func MaxIncrSeq(nums []int) int {
    max := 0
    arr := make([][]int, 0, len(nums))
    for _, num := range nums {
        bj := false
        for j := 0; j < max; j++ {
            if num < arr[j][len(arr[j])-1] {
                t := make([]int, len(arr[j]))
                copy(t, arr[j-1])
                t[len(t)-1] = num
                arr[j] = t
                bj = true
                break
            }
        }
        if !bj {
            t := make([]int, max+1)
            if max != 0 {
                copy(t, arr[len(arr)-1])
            }
            t[max] = num
            arr = append(arr, t)
            max = len(arr)
        }
    }
    return max
}

func MaxIncrSeqSize(nums []int) int {
    arr := make([]int, len(nums))
    for i := 0; i < len(arr); i++ {
        arr[i] = math.MaxInt32
    }
    max := 0
    for _, num := range nums {
        for i := 0; i < len(arr); i++ {
            if arr[i] > num {
                arr[i] = num
                if i+1 > max {
                    max = i + 1
                }
                break
            }
        }
    }
    return max
}