代码随想录算法训练营第52天|● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

300. 最长递增子序列

已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -10(4) <= nums[i] <= 10(4)

进阶：

• 你能将算法的时间复杂度降低到 O(n log(n)) 吗?

代码

func lengthOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    for i := 0; i < n; i++ {
        dp[i] = 1
    }
    result:=1
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                dp[i] = max(dp[j]+1, dp[i])
            }
            if dp[i]>result{
                result=dp[i]
            }
        }
    }
    return result
}

674. 最长连续递增序列

已解答
简单
相关标签
相关企业
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
示例 2：
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。

提示：

• 1 <= nums.length <= 10(4)
• -10(9) <= nums[i] <= 10(9)

代码

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

718. 最长重复子数组

中等
相关标签
相关企业
提示
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1：
输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1] 。
示例 2：
输入：nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出：5

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 100

思路

1. 确定dp数组（dp table）以及下标的含义
   dp[i][j] ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为dp[i][j]。
2. 确定递推公式
   根据dp[i][j]的定义，dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
   即当A[i - 1] 和B[j - 1]相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1;
3. dp数组如何初始化
   根据dp[i][j]的定义，dp[i][0] 和dp[0][j]其实都是没有意义的！
   但dp[i][0] 和dp[0][j]要初始值，因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
   所以dp[i][0] 和dp[0][j]初始化为0。
4. 确定遍历顺序
   外层for循环遍历A，内层for循环遍历B
5. 举例推导dp数组

代码

func findLength(nums1 []int, nums2 []int) int {
    n1 := len(nums1)
    n2 := len(nums2)
    //dp[i][j]表示0~i-1和0~j-1位置的最大子数组
    dp := make([][]int, n1+1) 
    for i := 0; i <= n1; i++ {
        dp[i] = make([]int, n2+1)
    }
    res := 0
    for i := 0; i < n1; i++ {
        for j := 0; j < n2; j++ {
            if nums1[i] == nums2[j] {
                dp[i+1][j+1] = dp[i][j] + 1
            }
            res = max(res, dp[i+1][j+1])
        }
    }
    return res
}