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

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 给定数组的最长严格上升子序列的长度。
 * @param arr int整型一维数组 给定的数组
 * @return int整型
 */
func LIS(arr []int) int {
	// write code here
	if len(arr) < 2 {
		return len(arr)
	}
	dpLen := make([]int, len(arr))
	dpLen[0] = 1
	for i := 1; i < len(arr); i++ {
		smallerValPos := -1
		tmp := 0
		for j := i - 1; j >= 0; j-- {
			if arr[i] >= arr[j] {
				//i和j之间是递增序列关系;
				if dpLen[j] > tmp {
					smallerValPos = j
					tmp = dpLen[j]
				}
			}
		}
		//前面符合条件的最长序列结尾元素位置a
		if smallerValPos == -1 { //没有更小的元素位置
			dpLen[i] = 1
		} else {
			dpLen[i] = tmp + 1
		}
	}
	//遍历一次拿到最长子序列的长度和结尾元素位置
	mxLen := 0
	for i := 0; i < len(dpLen); i++ {
		if dpLen[i] > mxLen {
			mxLen = dpLen[i]
		}
	}
	return mxLen
}