代码随想录算法训练营第五十三天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和

**代码随想录算法训练营第五十三天**

##1143. 最长公共子序列### 题目描述给定两个字符串 `s1` 和 `s2`,找到它们的最长公共子序列（LCS）。如果有多个长度相同的 LCS，则返回其中一个。

### 示例* 输入:`s1 = "AGGTAB"、`$s2 = "GXTXAYB"`，输出： `"GTAB"`
* 输入:`s1 = "ABC"、`$s2 = "DEF"`，输出： `""`

### 思路最长公共子序列（LCS）问题可以使用动态规划来解决。我们首先定义一个2D 数组 `dp`，其中 `dp[i][j]` 表示 `s1[0..i-1]` 和 `s2[0..j-1]` 的 LCS 的长度。

###代码

def longestCommonSubsequence(s1: str, s2: str) -> str:
 m, n = len(s1), len(s2)
 # dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的 LCS 的长度 dp = [[0] * (n +1) for _ in range(m +1)]
 # 初始化第一行和第一列 for i in range(m +1):
 dp[i][0] =0 for j in range(n +1):
 dp[0][j] =0 # 填充dp数组 for i in range(1, m +1):
 for j in range(1, n +1):
 if s1[i -1] == s2[j -1]:
 dp[i][j] = dp[i -1][j -1] +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
 # 回溯求LCS lcs = []
 i, j = m, n while i >0 and j >0:
 if s1[i -1] == s2[j -1]:
 lcs.append(s1[i -1])
 i -=1 j -=1 elif dp[i -1][j] > dp[i][j -1]:
 i -=1 else:
 j -=1 # 返回LCS return "".join(reversed(lcs))

##1035. 不相交的线### 题目描述给定一个数组 `points`，其中每个元素都是一个点的坐标 `(x, y)`。请找出不相交的线段数。

### 示例* 输入:`points = [[1,1],[1,2],[3,4]]`,输出： `2`
* 输入:`points = [[1,1],[2,2],[3,3]]`,输出： `0`

### 思路不相交的线段数可以使用贪婪算法来解决。我们首先根据 x 坐标对点进行排序，然后遍历每个点，计算出它所在的线段的数量。

###代码

def maxUncrossedLines(points):
 m = len(points)
 # dp[i][j] 表示前 i 个点和第 j 个点之间不相交的线段数 dp = [[0] * m for _ in range(m)]
 # 初始化第一行和第一列 for i in range(m):
 dp[i][i] =1 # 填充dp数组 for length in range(2, m +1):
 for i in range(m - length +1):
 j = i + length -1 # 如果两点的 x 坐标相同，则不相交的线段数为前一对点之间的线段数 if points[i][0] == points[j][0]:
 dp[i][j] = dp[i][j]
 else:
 # 否则，取前一对点之间的线段数和当前点所在的线段数的最大值 for k in range(i, j):
 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k +1][j])
 # 返回不相交的线段数 return dp[0][m -1]

##53. 最大子序和### 题目描述给定一个整数数组 `nums`，请找出最大子序列和。

### 示例* 输入:`nums = [-2,1,-3,4,-1,2,1,-5,4]`,输出： `6`
* 输入:`nums = [1]`,输出： `1`

### 思法最大子序列和可以使用动态规划来解决。我们首先定义一个数组 `dp`，其中 `dp[i]` 表示前 `i` 个数字的最大子序列和。

###代码

def maxSubarraySum(nums):
 m = len(nums)
 # dp[i] 表示前 i 个数字的最大子序列和 dp = [0] * (m +1)
 # 初始化第一行 for i in range(m +1):
 dp[i] = float('-inf')
 # 填充dp数组 for i in range(1, m +1):
 dp[i] = max(dp[i -1], nums[i -1] + dp[i -1])
 # 返回最大子序列和 return dp[m]

以上是本文对1143. 最长公共子序列、1035. 不相交的线、53. 最大子序和这三个算法题的解答。