常用算法笔记 > 动态规划
最长上升子序列(LIS)

问题描述:

给定长度为n的序列a,从a中抽取出一个子序列,这个子序列需要单调递增。

问最长的上升子序列(LIS)的长度。
 输入:1,5,3,4,6,9,7,8

   输出 :1,3,4,6,7,8,长度为6。


  

func maxLen(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	numsLen := len(nums)
	max := 1
	//subLenTable记录以下标为i为结尾的子序列长度, 初始化该数组每个原始长度为1
	subLenTable := make([]int, numsLen)
	for j := 0; j < numsLen; j++ {
		subLenTable[j] = 1
	}

	//
	for i := 1; i < numsLen; i++ {
		//查询subLenTable前i-1个元素,找到比当前元素小的最大子序列然后将当前元素插入
		//并且更新查询表
		for j := i - 1; j >= 0; j-- {
			if nums[j] <= nums[i] && subLenTable[i] <= subLenTable[j] {
				subLenTable[i] = subLenTable[j] + 1
				if subLenTable[i] > max {
					max = subLenTable[i]
				}
			}
		}
	}
	return max
}