题解 | #最长上升子序列(一)#

package main

import (
    "sort"
)
// 贪心
func LIS( arr []int ) int {
    ans := []int{}
    for i := 0; i < len(arr); i++ {
        if len(ans) == 0 {
            ans = append(ans, arr[i])
            continue    
        }
        index := sort.SearchInts(ans, arr[i])
        if index == len(ans) {
            ans = append(ans, arr[i])
        } else {
            ans[index] = arr[i]
        }
    }
    return len(ans)
}