题解 | 最长递增子序列

package main

import (
	"fmt"
)

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
func main() {
	num := 0
	for {
		n, _ := fmt.Scan(&num)
		if n == 0 {
			break
		} else {
			arr := make([]int, num)
			for i := 0; i < num; i++ {
				fmt.Scan(&arr[i])
			}
			res := f(arr)
			for i := 0; i < len(res); i++ {
				if i == len(res)-1 {
					fmt.Println(res[i])
				} else {
					fmt.Printf("%d ", res[i])
				}
			}
		}
	}
}

func f(arr []int) []int {
	end := []int{arr[0]} // end数组每个值的含义end[i]，长度为i+1,对应arr所在位置的最小值
	dp := make([]int, len(arr)) // 记录每个位置的长度
	dp[0] = 1 // 初始时，0位置对应的长度为1，最大长度为1，所在位置为0
	maxvalue := dp[0] // 递增系序列最大值
	index := 0 // 递增系序列最大值所在位置
	for i := 1; i < len(arr); i++ {
		k := find(end, arr[i]) // 在end数组中，找到大于arr[i]的第一个位置
		if k == len(end) { // k右边越界，表示在当前end数组中找不到比arr[i]大的数
			end = append(end, arr[i])  // 添加arr[i],表示以arr[i]结尾，最长递增子序列长度为k+1
			dp[i] = k + 1 // 表示以arr[i]结尾，最长递增子序列长度为k+1
			maxvalue = dp[i]
			index = i
		} else if k < len(end) && end[k] > arr[i] { // 找到1个可比较的位置，对以下2种情况合并：
		  // 情况1: 能够找到一个位置，这个位置大于等于arr[i]，只有大于大时候需要更新
		  // 情况2: 左边越界，此时k返回为0，这个位置要么end[k] > arr[i]进行更新，要么保留返回值
			end[k] = arr[i]
			dp[i] = k + 1
			if maxvalue == k+1 { 
			  //当递增系序列在最大长度上进行更新较小的arr[i]值，对应的位置也需要修改
				index = i
			}
		} else {
		}
	}

	res := make([]int, maxvalue)
	for i, j := index, 0; i >= 0 && maxvalue != 0; i-- {
		// 每次按最大长度，
	    // 每次只取最后的一个值，肯定为最小值
		if dp[i] == maxvalue {
			maxvalue--
			res[len(res)-j-1] = arr[i]
			j++
		}
	}

	return res
}
// find方法，数组中的值升序，且没有重复值
// 返回值表示
// 右边越界，找不到对应的值
// 返回[0..len(end)-1] 在end数组中可以找到一个位置，这个位置>=target
// 例外，返回为0时，可能表示找到，也可能表示找不到，左边越界。
func find(end []int, target int) int {
	l, r := 0, len(end)-1
	for l <= r {
		mid := (r-l)/2 + l
		if end[mid] > target {
			r = mid - 1
		} else if end[mid] == target {
			return mid
		} else {
			l = mid + 1
		}
	}
	return l
}