算法训练营day44(补),动态规划12

func max(a, b int) int {

  if a > b {

    return a

  }

  return b

}

//300. 最长递增子序列

func lengthOfLIS(nums []int) int {

  dp := make([]int, len(nums))

  for i := range dp {

    dp[i] = 1

  }

  for i := 1; i < len(nums); i++ {

    for j := 0; j < i; j++ {

        //收集所有子序列

      if nums[i] > nums[j] {

        dp[i] = max(dp[j]+1, dp[i])

      }

    }

  }

  num := 0

//求最长

  for i := 0; i < len(nums); i++ {

    num = max(num, dp[i])

  }

  return num

}

//674. 最长连续递增序列

func findLengthOfLCIS(nums []int) int {

  dp := make([]int, len(nums))

  for i := range dp {

    dp[i] = 1

  }

  for i := 1; i < len(nums); i++ {

   //因为要求连续，遍历1次即可

    if nums[i] > nums[i-1] {

      dp[i] = dp[i-1] + 1

    }

  }

  num := 0

//求最长

  for i := 0; i < len(nums); i++ {

    num = max(num, dp[i])

  }

  return num

}

//718. 最长重复子数组

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

  dp := make([][]int, len(nums1)+1)

  for i := 0; i <= len(nums1); i++ {

    dp[i] = make([]int, len(nums2)+1)

  }

  num := 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

      }

     //求最长

      if dp[i][j] > num {

        num = dp[i][j]

      }

    }

  }

  return num

}