每日一题——最长上升子序列与最长回文子串

最长上升子序列与最长回文子串 最长上升子序列(LIS)问题描述动态规划解法代码实现时间复杂度分析示例分析 最长回文子串问题描述动态规划解法代码实现 (动态规划法)中心扩展法代码实现 (中心扩展法)时间复杂度分析示例分析 总结

最长上升子序列(LIS) 问题描述

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

严格上升子序列的定义是：当且仅当该序列不存在两个下标 i 和 j 满足 i < j 且 arr[i] ≥ arr[j]。

动态规划解法

我们使用一个dp数组，其中dp[i]表示以第i个元素结尾的最长上升子序列的长度。

算法步骤：

初始化dp数组，所有元素设为1（因为单个元素的子序列长度为1）对于每个位置i，遍历其前面的所有位置j： 如果arr[j] < arr[i]，说明可以将arr[i]接在以arr[j]结尾的上升子序列后面此时dp[i] = max(dp[i], dp[j] + 1) 最终结果是dp数组中的最大值 代码实现 /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @param arrLen int arr数组长度 * @return int整型 */ int LIS(int* arr, int arrLen) { if (arrLen == 0) return 0; int* dp = (int*)malloc(arrLen * sizeof(int)); // 初始化 dp 数组 for (int i = 0; i < arrLen; i++) { dp[i] = 1; } // 动态规划计算 for (int i = 1; i < arrLen; i++) { for (int j = 0; j < i; j++) { if (arr[j] < arr[i]) { dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1; } } } // 找到 dp 数组中的最大值 int result = 0; for (int i = 0; i < arrLen; i++) { result = (result > dp[i]) ? result : dp[i]; } // 释放 dp 数组 free(dp); return result; } 时间复杂度分析 时间复杂度：O(n²)，其中n是数组长度。两层嵌套循环。空间复杂度：O(n)，需要一个长度为n的dp数组。 示例分析

输入：[6,3,1,5,2,3,7]

过程：

dp[0] = 1 (只有元素6)dp[1] = 1 (只有元素3)dp[2] = 1 (只有元素1)dp[3] = 2 (序列[1,5])dp[4] = 2 (序列[1,2])dp[5] = 3 (序列[1,2,3])dp[6] = 4 (序列[1,2,3,7])

最终结果：4，对应的最长上升子序列为[1,2,3,7]

最长回文子串 问题描述

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），计算其中最长回文子串的长度。

动态规划解法

我们使用一个二维数组dp，其中dp[i][j]表示子串A[i…j]是否为回文串。

算法步骤：

初始化：所有单个字符都是回文串，dp[i][i] = 1检查长度为2的子串：如果A[i] == A[i+1]，则dp[i][i+1] = 1检查长度大于2的子串：如果A[i] == A[j]且dp[i+1][j-1] = 1，则dp[i][j] = 1记录最长回文子串的长度 代码实现 (动态规划法) #include <stdio.h> #include <string.h> int getLongestPalindrome(char* A) { int n = strlen(A); int dp[n][n]; memset(dp, 0, sizeof(dp)); int maxLen = 1; // 单个字符是回文 for (int i = 0; i < n; i++) { dp[i][i] = 1; } // 检查长度为2的子串 for (int i = 0; i < n - 1; i++) { if (A[i] == A[i + 1]) { dp[i][i + 1] = 1; maxLen = 2; } } // 检查长度大于2的子串 for (int len = 3; len <= n; len++) { for (int i = 0; i < n - len + 1; i++) { int j = i + len - 1; if (A[i] == A[j] && dp[i + 1][j - 1]) { dp[i][j] = 1; maxLen = len; } } } return maxLen; } 中心扩展法

除了动态规划，还可以使用中心扩展法解决此问题：

遍历字符串的每个字符，以其为中心向两边扩展需要考虑两种情况：以单个字符为中心和以两个字符之间为中心记录最长回文子串的长度 代码实现 (中心扩展法) #include <stdio.h> #include <string.h> int expandAroundCenter(char* s, int left, int right) { while (left >= 0 && right < strlen(s) && s[left] == s[right]) { left--; right++; } return right - left - 1; // 返回回文子串的长度 } int getLongestPalindrome(char* A) { int n = strlen(A); int maxLen = 0; for (int i = 0; i < n; i++) { // 单字符中心 int len1 = expandAroundCenter(A, i, i); // 双字符中心 int len2 = expandAroundCenter(A, i, i + 1); maxLen = (len1 > maxLen) ? len1 : maxLen; maxLen = (len2 > maxLen) ? len2 : maxLen; } return maxLen; } 时间复杂度分析

动态规划法：

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

中心扩展法：

时间复杂度：O(n²)空间复杂度：O(1) 示例分析

输入：“ababc”

过程（以中心扩展法为例）：

以’a’为中心，最长回文子串为"a"，长度为1以’a’和’b’之间为中心，无回文以’b’为中心，最长回文子串为"b"，长度为1以’b’和’a’之间为中心，无回文以’a’为中心，最长回文子串为"aba"，长度为3以’a’和’b’之间为中心，无回文以’b’为中心，最长回文子串为"bab"，长度为3以’b’和’c’之间为中心，无回文以’c’为中心，最长回文子串为"c"，长度为1

最终结果：3，对应的最长回文子串为"aba"或"bab"

总结

这两个问题都是动态规划的经典应用，体现了动态规划"将问题分解为子问题，并存储子问题的解以避免重复计算"的思想。

最长上升子序列：通过dp[i]存储以第i个元素结尾的最长上升子序列长度最长回文子串：通过dp[i][j]存储子串A[i…j]是否为回文串

此外，最长回文子串还展示了如何通过中心扩展法优化空间复杂度，这是一个很好的例子，说明有时候灵活思考可以找到比标准动态规划更高效的解法。