算法训练（leetcode）二刷第三十八天|1143.最长公共子序列、1035.不相交的线、53.最大子数组和、

刷题记录 1143. 最长公共子序列1035. 不相交的线53. 最大子数组和动态规划优化版 392. 判断子序列

1143. 最长公共子序列

leetcode题目地址

本题和300. 最长递增子序列相似（题解）。

使用动态规划：

dp数组含义：dp[i][j]表示 以text1[i-1]结尾的子串A 和 以text2[j-1]结尾的子串B 的最长公共子序列的长度。思路同300. 最长递增子序列，每个状态更新基于前面的状态，为了防止越界，dp数组下标从1开始。状态转移方程： 当 text1[i-1] == text2[j-1] 时，dp[i][j] = dp[i-1][j-1] + 1;当 text1[i-1] == text2[j-1] 时，dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 这里解释一下 max(dp[i-1][j], dp[i][j-1]) 的含义：由于dp数组存储的是两个子串的最长公共子序列的长度，当两个子串的单个字符不匹配时，对应下标处的dp值要赋值为前面子串的匹配情况取最长，即dp[i-1][j]表示以text1[i-2]结尾的子串A和以text2[j-1]结尾的子串B 的最长公共子序列的长度，dp[i][j-1]表示以text1[i-1]结尾的子串A和以text2[j-2]结尾的子串B 的最长公共子序列的长度。

时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)

// java class Solution { public int longestCommonSubsequence(String text1, String text2) { int len1 = text1.length(), len2 = text2.length(); char[] arr1 = text1.toCharArray(), arr2 = text2.toCharArray(); int[][] dp = new int[len1+1][len2+1]; for(int i = 1; i <= len1; i++){ for (int j = 1; j <= len2; j++){ if(arr1[i-1] == arr2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; } else{ dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } // System.out.print(dp[j] + " "); } // System.out.println(); } return dp[len1][len2]; } } 1035. 不相交的线

leetcode题目地址

本题其实与上一题1143. 最长公共子序列的思路完全一致。题目的描述时要求找不相交的线的最大连线数，而不相交的线其实就是找两个序列的公共子序列（不相交就是两个子序列在原序列中相对顺序一致）。

时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)

// java class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int len1 = nums1.length, len2 = nums2.length; int[][] dp = new int[len1+1][len2+1]; for(int i=1; i<=len1; i++){ for(int j=1; j<=len2; j++){ if(nums1[i-1] == nums2[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; } else{ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[len1][len2]; } } 53. 最大子数组和

leetcode题目地址

dp数组含义： dp[i]表示以nums[i]结尾（包含）的最大子数组和

状态转移方程： dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);

dp[i-1] + nums[i]表示上一个（以nums[i-1]结尾的）子序列加入当前nums[i]nums[i]表示从当前元素开始从头计算（仅包含当前元素的子序列）

初始化： dp[i]表示以nums[i]结尾（包含）的最大子数组和，因此dp[0]初始化为nums[0]，后面状态均为0.

时间复杂度： O ( n ) O(n) O(n) 空间复杂度： O ( n ) O(n) O(n)

动态规划 // java class Solution { public int maxSubArray(int[] nums) { int len = nums.length; int[] dp = new int[len]; dp[0] = nums[0]; int result = nums[0]; for(int i=1; i<len; i++){ dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); result = Math.max(dp[i], result); } return result; } } 优化版

可以看到在动规中每个状态的更新都仅依赖于前一个状态，因此无需使用数组，仅使用一个变量来记录前一个状态。

时间复杂度： O ( n ) O(n) O(n) 空间复杂度： O ( 1 ) O(1) O(1)

// java class Solution { public int maxSubArray(int[] nums) { int len = nums.length; int res = nums[0]; int result = nums[0]; for(int i=1; i<len; i++){ res = Math.max(res + nums[i], nums[i]); result = Math.max(res, result); } return result; } } 392. 判断子序列

leetcode题目地址

本题本质上依旧是寻找最长公共子序列。给定s和t，判断s是否是t的子序列，也就是查看s和t的最长公共子序列长度是否等于s的长度。

dp数组含义： dp[i][j]表示 以s[i-1]结尾的子串A 和 以t[j-1]结尾的子串B 的最长公共子序列。状态转移方程： 当s[i-1] == t[j-1]时，dp[i][j] = dp[i-1][j-1] + 1;当s[i-1] != t[j-1]时，dp[i][j] = dp[i][j-1];

这里不匹配时为什么是 dp[i][j] = dp[i][j-1] 而不是 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) 因为是在t中查找s是否是子序列，因此在不匹配时，只能删除t中的字符来查看分别以s[i-1]和t[j-2]结尾的子串的匹配情况。

而1143. 最长公共子序列不给定谁为子串，因此需要分别考虑各自为另一个字符串的子串的情况。

时间复杂度： O ( n ∗ m ) O(n*m) O(n∗m) 空间复杂度： O ( n ∗ m ) O(n*m) O(n∗m)

// java class Solution { public boolean isSubsequence(String s, String t) { char[] sArry = s.toCharArray(); char[] tArry = t.toCharArray(); int len1 = s.length(), len2 = t.length(); int[][] dp = new int[len1+1][len2+1]; for(int i=1; i<=len1; i++){ for(int j=1; j<=len2; j++){ if(sArry[i-1] == tArry[j-1]){ dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = dp[i][j-1]; } // System.out.print(dp[i][j] + " "); } // System.out.println(); } return dp[len1][len2] == len1; } }