【代码随想录刷题记录】1143.最长公共子序列 、 1035.不相交的线 、53. 最大子序和

**代码随想录刷题记录**

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

#### 题目描述给定两个字符串 `s1` 和 `s2`,找到它们的最长公共子序列（LCS）。你可以假设这两个字符串都只包含小写字母。

#### 示例1:

输入：`s1 = "abcde", s2 = "ace"`，输出：`"a c e"`

#### 示例2:

输入：`s1 = "abc", s2 = "cab"`，输出：`"abc"`

#### 思路我们可以使用动态规划来解决这个问题。首先，我们需要定义一个二维数组 `dp` 来存储两个字符串的最长公共子序列长度。

def longestCommonSubsequence(s1, s2):
 m, n = len(s1), len(s2)
 dp = [[0] * (n +1) for _ in range(m +1)]

 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 return "".join(reversed(lcs))

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

#### 题目描述给定一个数组 `points`，其中每个元素都是一个长度为2 的整数数组，表示一条线段的端点。返回不相交的线段数量。

#### 示例1:

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

#### 示例2:

输入：`points = [[1,2],[2,3],[4,5]]`,输出：`3`

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

def maxUncrossedLines(points):
 n = len(points)
 dp = [[0] * n for _ in range(n)]

 # 初始化第一行和第一列 for i in range(n):
 dp[i][i] =1 # 对角线元素为1 for length in range(2, n +1):
 for left in range(n - length +1):
 right = left + length -1 dp[left][right] = max(dp[left][right], dp[left][right -1])

 # 如果当前线段不相交，则增加dp值 if points[right][0] > points[left][1]:
 dp[left][right] = max(dp[left][right], dp[left +1][right] +1)

 return dp[0][-1]

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

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

#### 示例1:

输入：`nums = [-2,1,-3,4,-1,2,1,-5,4]`,输出：`6`

#### 示例2:

输入：`nums = [1]`,输出：`1`

#### 思路我们可以使用动态规划来解决这个问题。首先，我们需要定义一个一维数组 `dp` 来存储最大子序列和。

def maxSubarraySum(nums):
 n = len(nums)
 dp = [0] * (n +1)

 # 初始化第一行 for i in range(n):
 dp[i +1] = max(dp[i], nums[i])

 return dp[-1]

### **总结**

在本文中，我们分别解决了1143. 最长公共子序列、1035. 不相交的线和53. 最大子序和三个问题。我们使用动态规划和贪婪算法来解决这些问题，实现了高效且准确的结果。

### **参考代码**

*1143. 最长公共子序列： 不相交的线： 最大子序和：