1143. 最长公共子序列
最长公共子序列（Longest Common Subsequence，简称 LCS)
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-common-subsequence
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
def longestCommonSubsequence(s1: str, s2: str) -> int:
m = len(s1)
n = len(s2)
dp = [[0] * (n+1) for i in range(m+1)]
# // 定义：s1[0..i-1] 和 s2[0..j-1] 的 lcs 长度为 dp[i][j]
# // 目标：s1[0..m-1] 和 s2[0..n-1] 的 lcs 长度，即 dp[m][n]
# // base case: dp[0][..] = dp[..][0] = 0
for i in range(1, m+1):
for j in range(1, n+1):
# // 现在 i 和 j 从 1 开始，所以要减一
if s1[i-1] == s2[j-1]:
# // s1[i-1] 和 s2[j-1] 必然在 lcs 中
dp[i][j] = 1+dp[i-1][j-1]
else:
# s1[i-1] 和 s2[j-1] 至少有一个不在 lcs 中
# 还有一种dp[i-1][j-1]包含在下面两种中，所以可忽略。
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
def maxSubArray(self, nums: List[int]) -> int:
dp = [0 for i in range(len(nums))]
dp[0] = nums[0]
# 以nums[i]为结尾的「最大子数组和」为dp[i]。
for i in range(len(nums[1:])):
dp[i+1] = max(dp[i]+nums[i+1], nums[i+1])
return max(dp)
