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

package main

/**
 * retrun the longest increasing subsequence
 * @param arr int整型一维数组 the array
 * @return int整型一维数组
*/
type LNode struct {
	val int
	pre *LNode
}

func LIS(arr []int) []int {
	dp := make([]*LNode, 0)
	for _, a := range arr {
		l := 0
		r := len(dp) - 1
		for l <= r {
			mid := (l + r) / 2
			if a > dp[mid].val {
				l = mid + 1
			} else {
				r = mid - 1
			}
		}
		if l == 0 && len(dp) > 0 && dp[l].val <= a {
			continue
		}
		node := &LNode{val: a}
		if r >= 0 {
			node.pre = dp[r]
		}
		if l < len(dp) {
			dp[l] = node
		} else {
			dp = append(dp, node)
		}
	}
	a := make([]int, 0)
	if len(dp) > 0 {
		p := dp[len(dp)-1]
		for p != nil {
			a = append(a, p.val)
			p = p.pre
		}
		n := len(a)
		for i := 0; i < n/2; i++ {
			a[i], a[n-1-i] = a[n-1-i], a[i]
		}
	}
	return a
	// write code here
}