最长递增子序列

1. 题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

2. 思路

1. 思路一
   • DFS
   • 对于每个元素，尝试加入递增子序列；如果后面能找到比这个元素达到的，那么继续往后找
2. 思路二
   • DFS+缓存

3. 实现

3.1. DFS

func lengthOfLIS(nums []int) int {
	count := 0
	maxCount := 0

	lengthOfLISDFS(nums, 0, &count, &maxCount)
	return maxCount
}

func lengthOfLISDFS(nums []int, index int, count *int, maxCount *int) {
	for i := index; i < len(nums); i++ {
		if (nums[i] > nums[index] || *count == 0) && len(nums)-i+*count > *maxCount {
			*count++
			*maxCount = Max(*maxCount, *count)

			lengthOfLISDFS(nums, i, count, maxCount)

			*count--
		}
	}
}

3.2. DFS+缓存

func lengthOfLIS(nums []int) int {
    memo := make(map[[2]int]int, 0)

    return lengthOfLISDFS(nums, 0, math.MinInt32, memo)
}

func lengthOfLISDFS(nums []int, index int, prev int, memo map[[2]int]int) int {
    key := [2]int{index, prev}
    count, ok := memo[key]
    if ok {
        return count
    }

    if index >= len(nums) {
        return 0
    }


    for i := index; i < len(nums); i++{
        if nums[i] > prev {
            count = max(count, 1+lengthOfLISDFS(nums, i+1, nums[i], memo))
        }
    }

    memo[key] = count
    return count
}

func max(a, b int) int {
    if a > b {
        return a
    }

    return b
}

4. 参考

• 300. 最长递增子序列 - 力扣（LeetCode）