【Golang必备算法】子序列问题

子序列问题

子序列问题分为连续和不连续，不连续递增子序列的跟前0-i 个状态有关，连续递增的子序列只跟前一个状态有关，所以不连续的需要两层for循环

300. 最长递增子序列（不连续）

func lengthOfLIS(nums []int) int {
    if len(nums) == 1{
        return 1
    }
    res := 1
    //dp[i] 表示i之前包括i的最长上升子序列的长度
    dp := make([]int,len(nums))
    //初始化，每个dp[i]初始至少为1
    for i:=0;i<len(nums);i++{
        dp[i] = 1
    }

    dp[0] = 1
    for i:=1;i<len(nums);i++{
        for j:=0;j<i;j++{
            if nums[i] > nums[j]{
                dp[i] = max(dp[i],dp[j]+1)         
            }
        }
        //保留dp数组中的最大值
        if dp[i] > res{
            res = dp[i]
        }
    }
    return res
}

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

1143. 最长公共子序列

func longestCommonSubsequence(text1 string, text2 string) int {
    //dp[i][j]代表长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
    dp := make([][]int,len(text1)+1)
    for i:=0;i<=len(text1);i++{
        dp[i] = make([]int,len(text2)+1)
    }

    for i:=1;i<=len(text1);i++{
        for j:=1;j<=len(text2);j++{
            if text1[i-1] == text2[j-1]{
                dp[i][j] = dp[i-1][j-1] + 1
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
return dp[len(text1)][len(text2)]

}

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

674. 最长连续递增序列

func findLengthOfLCIS(nums []int) int {
    dp := make([]int,len(nums))
    for k,_:=range dp{
        dp[k]=1
    }
    res := 1
    for i:=1;i<len(nums);i++{
        if nums[i] > nums[i-1]{
            dp[i] = dp[i-1]+1
        }
        if dp[i] > res{
            res = dp[i]
        }
    }
    return res
}

718. 最长重复子数组

func findLength(nums1 []int, nums2 []int) int {

    //dp[i][j]代表以nums1[i-1]为结尾的A，和以nums2[j-1]为结尾的B，最长重复子数组长度是dp[i][j]
    dp := make([][]int,len(nums1)+1)
    for k,_:=range dp{
        dp[k] = make([]int,len(nums2)+1)
    }
    res := 0
    for i:=1;i<=len(nums1);i++{
        for j:=1;j<=len(nums2);j++{
            if nums1[i-1] == nums2[j-1]{
                dp[i][j] = dp[i-1][j-1] + 1
                res = max(res,dp[i][j])
            }
        }
    }
    return res
}

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