最长递增子序列

什么是最长递增序列

• 比如给定的list是[10,9,2,5,3,7,101,18] 那么最大的最长递增序列是[2,3,7,101]
  • 想要实现就要知道这个递增，并非要求连续递增，也就是说，中间不符合的
• 给定[0,1,0,3,2,3]，那么最长递增子序列[0,1,2,3]
• 最后返回值，给定对应的最长子序列的长度即可

按照贪心 + 二分差的实现思路

• 初始化子序列列表
• 遍历给定列表
  • 每个数判断在子序列中的位置
  • 超出已有位置，追加到子序列
  • 小于子序列中某个位置的值，替换该位置即可

具体实现

方法一：相对更优（贪心 + 二分查）

• 时间复杂度： nlogn

golang
func longestList(arr []int) int {
    list := []int
    for _, num := range arr {
        l,r := 0, len(list)
        for l < r {
            mid = l + (r-l)/2
            if list[mid] < num {
                l = mid + 1
            }else{
                r = mid
            }
        }

        if l = len(list) {
            list = append(list, num)
        }else{
            list[l] = num
        }
    }
    return len(list)
}

方法二： 动态规划

• 实现思路
  • 默认初始所有的数都是最长序列的最后一个值，也就是默认长度为1
  • 然后
• 时间复杂度 ： n*n

golang
func lengthOfLIS(nums []int) int {
    res := 0
    n := len(nums)
    dp := make([]int, n)

    for i := 0;i < n;i++ {
        dp[i] = 1
        for j := 0; j < i;j++ {
            if nums[j] < nums[i] {
                dp[i] = max(dp[i], dp[j] + 1)
            }
        }

        res = max(res, dp[i])
    }
    return res
}

func max(i, j int) int{
    if i > j {
        return i
    }
    return j
}