(31)Go动态规划求最长上升序列

状态定义和状态转移方程如上图
func max(i1, i2 int) int {
    if i1 > i2 {
        return i1
    }
    return i2
}

方法1： 记忆化搜索
// 时间复杂度O(n^2)
// 空间复杂度O(n)
func lengthOfLIS2(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }

    // [0...index]中包含nums[index]的最长上升子序列长度
    memo := make([]int, n)

    maxV := 1
    for i := 0; i < n; i++ {
        maxV = max(maxV, tryLIS2(nums, i, n, memo))
    }
    return maxV
}

// 求[0...index]中包含nums[index]的最长上升子序列长度
func tryLIS2(nums []int, index, n int, memo []int) int {
    if memo[index] != 0 {
        return memo[index]
    }

    // 递归终止条件
    if index == 0 {
        memo[index] = 1
        return 1
    }

    // 递归过程
    maxV := 1
    for i := index - 1; i >= 0; i-- {
        if nums[index] > nums[i] {
            maxV = max(maxV, 1+tryLIS2(nums, i, n, memo))
        }
    }
    memo[index] = maxV
    return maxV
}

由状态方程可以看出[0...index]依赖于[0...index-1]求解，
可以先求问题[0...0],[0...1]...，一步步扩大,最终求得[0...n-1]的答案
方法2： 动态规划
// 时间复杂度O(n^2)
// 空间复杂度O(n)
func lengthOfLIS3(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }

    // [0...index]中包含nums[index]的最长上升子序列长度
    memo := make([]int, n)
    memo[0] = 1

    res := 1
    for i := 1; i < n; i++ {
        memo[i] = 1
        for j := i - 1; j >= 0; j-- {
            if nums[i] > nums[j] {
                memo[i] = max(memo[i], 1+memo[j])
            }
        }
        res = max(res, memo[i])
    }
    return res
}

方法1，2提交leetcode，通过

该题目用二分查找法速度更快，实现如下：
// 时间复杂度是O(nlogn)
// 空间复杂度O(n)
func lengthOfLIS(nums []int) int {
    n := len(nums)
    if n < 2 {
        return n
    }

    // buf[endI]: 扫描到num[index]时,最长上升子序列的"结尾"的最小值
    // 因为可能有多个最长上升子序列,结尾值有大有小,存储那个结尾值最小的
    // 后续数字只要比buf[endI]大,最长上升子序列长度+1
    // 若nusm[index]<=buf[endI],则将nums[index]覆盖到
    // 满足buf[j-1]<=nums[index]<=buf[j]的buf[j]位置
    // 寻找位置这一步用二分查找法,时间复杂度是logn,共n个元素,所以时间复杂度是O(nlogn)
    // 需要注意的是buf中存储的可能不是最长序列,也可能是,只是一个辅助求最长序列长度的数组
    buf := make([]int, n)
    buf[0] = nums[0]

    endI, maxL := 0, 1
    for i := 1; i < n; i++ {
        // nums[endI]为最长上升子序列的结尾
        if nums[i] > buf[endI] {
            maxL++
            endI++
            buf[endI] = nums[i]
        } else {
            // 二分查找法寻找位置
            l, r, mid := 0, endI, 0

            for l <= endI {
                mid = l + (r-l)/2
                if nums[i] <= buf[mid] { //左边
                    if mid == l || nums[i] >= buf[mid-1] {
                        buf[mid] = nums[i]
                        break
                    } else {
                        r = mid - 1
                    }
                } else { // 右边 nums[i]>buf[mid]
                    l = mid + 1
                }
            }
        }
    }
    return maxL
}

提交leetcode，通过

有bug欢迎指出