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

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

## **1143. 最长公共子序列**

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

### 示例1:

输入:`s1 = "abcde", s2 = "ace"`

输出:`"ace"`

### 示例2:

输入:`s1 = "abc", s2 = "cab"`输出:`"abc"`

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

###代码

def longestCommonSubsequence(s1, s2):
 m, n = len(s1), len(s2)
 # 初始化 dp 数组 dp = [[0] * (n +1) for _ in range(m +1)]
 # 填充 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 = []
 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 # 返回最长公共子序列 return "".join(reversed(lcs))

## **1035. 不相交的线**

### 题目描述给定一个数组 `points`，其中每个元素是两个整数的列表，表示一条线段。返回不相交的线段数量。

### 示例1:

输入:`points = [[1,2],[2,3],[3,4]]`

输出:`2`

### 示例2:

输入:`points = [[1,2],[4,5]]`

输出:`2`

### 思路我们可以使用贪婪算法来解决这个问题。首先，我们需要对线段进行排序，根据它们的 x 坐标。

然后，我们可以遍历线段，并计算每对线段之间的交点。如果两条线段不相交，则将它们添加到结果中。

###代码

def maxUncrossedLines(points):
 n = len(points)
 # 初始化 dp 数组 dp = [[0] * (n +1) for _ in range(n +1)]
 # 填充 dp 数组 for i in range(1, n +1):
 for j in range(i, n +1):
 if points[i -1][0] == points[j -1][0]:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1]) +1 else:
 dp[i][j] = max(dp[i -1][j], dp[i][j -1])
 # 返回不相交的线段数量 return dp[n][n]

## **53. 最大子序和**

### 题目描述给定一个整数数组 `nums`，返回最大子序列和。

### 示例1:

输入:`nums = [-2,1,-3,4,-1,2,1,-5,4]`

输出:`6`

### 思路我们可以使用动态规划来解决这个问题。首先，我们需要定义一个数组 `dp`，其中 `dp[i]` 表示以 `i` 为结尾的最大子序列和。

然后，我们可以遍历数组，并计算每个元素对应的 `dp` 值。如果当前元素大于0，则将其添加到前面的最大子序列中；否则，将其作为新的起始点。

###代码

def maxSubarraySum(nums):
 n = len(nums)
 # 初始化 dp 数组 dp = [0] * (n +1)
 # 填充 dp 数组 for i in range(1, n +1):
 if nums[i -1] >0:
 dp[i] = max(dp[i -1], nums[i -1])
 else:
 dp[i] = dp[i -1]
 # 返回最大子序列和 return max(dp)

以上是本文对1143. 最长公共子序列、1035. 不相交的线和53. 最大子序和三个问题的分析和代码实现。