1143、最长公共子序列

本题可以和718、最长重复子数组结合起来看

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

解题思路：

根据两个字符串的长度设置一个len1 * len2的二维数组。数组初始化第一行和第一列，即空字符串和另一串去比较公共子序列长度，自然是0，遍历从1，1开始（注意读字符串的时候要减1）

如果text1[i - 1] == text2[j - 1]，自然是等于dp[i - 1][j - 1] + 1。但与最长重复子数组不同的是，在最长公共子序列时不需要严格连续，可以有跳过，所以当不相等时之前的最大值会保留下来往后延续，dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);。在最长重复子数组中因为要求严格连续，当当前不相等的时候此后的计算要重新开始，所以需要将当前置为0，并设置一个额外的max值来记录dp中的最大值

53、最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分（不间断连续）。

解题思路：

设定动态规划数组，dp[i]的意思是以此数为终点的子数组（该数字也计算在内）的最大值，故dp[i]只能从两个方向推出来：要么是dp[i - 1] + nums[i]（加入先前的序列），要么是nums[i]本身（从头开始计算）。需要通过max来遍历数组获取最大值（最大值可能在过程中出现而不是最后一位）