代码随想录第53天|1143.最长公共子序列， 1035.不相交的线，53. 最大子序和

**代码随想录第53天**

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

今天，我们来讨论一个经典的问题：最长公共子序列（Longest Common Subsequence，LCS）。这个问题是计算两个字符串的最长公共子序列。

**1035. 不相交的线**

接着，我们会讨论一个与图论相关的问题：不相交的线。这个问题是求出在一个点集上画出的不相交线段的最大数量。

**53. 最大子序和**

最后，我们会讨论一个经典的动态规划问题：最大子序和。这个问题是求出一个数组中连续子数组的最大和。

###1143. 最长公共子序列#### 题目描述给定两个字符串 `s1` 和 `s2`，请找到它们的最长公共子序列（LCS）。

#### 示例* 输入：`s1 = "abcde", s2 = "ace"`
输出： `"a c e"`
* 输入：`s1 = "abc", s2 = "def"`
输出： `""`

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

####代码

def longestCommonSubsequence(s1, s2):
 m, n = len(s1), len(s2)
 # Initialize dp array dp = [[0] * (n +1) for _ in range(m +1)]
 # Fill up the dp array 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])
 # Reconstruct the LCS from the dp array 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 the LCS in the correct order return "".join(reversed(lcs))

###1035. 不相交的线#### 题目描述给定一个点集 `points`，请找到在这个点集上画出的不相交线段的最大数量。

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

#### 思路我们可以使用贪婪算法来解决这个问题。我们首先将所有点按照 x 坐标排序，然后遍历每个点，将其作为线段的起始点。

####代码

def maxUncrossedLines(points):
 n = len(points)
 # Initialize dp array dp = [[0] * (n +1) for _ in range(n +1)]
 # Fill up the dp array 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 the maximum number of non-intersecting lines return dp[n][n]

###53. 最大子序和#### 题目描述给定一个数组 `nums`，请找到其中的最大子序和。

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

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

####代码

def maxSubarraySum(nums):
 n = len(nums)
 # Initialize dp array dp = [0] * (n +1)
 # Fill up the dp array for i in range(1, n +1):
 if nums[i -1] > dp[i -1]:
 dp[i] = nums[i -1]
 else:
 dp[i] = dp[i -1] + nums[i -1]
 # Return the maximum subarray sum return max(dp)

以上就是本篇文章的全部内容。我们分别讨论了最长公共子序列、不相交的线和最大子序和三个问题，并给出了解决方案。