给定一个长度为N 数组a 和一个长度为M 的数组b。 请你求出它们的最长公共上升子序列长度为多少。
时间: 2024-05-19 09:16:10 浏览: 27
首先,我们可以将问题转化为最长公共子序列(LCS)问题。因为最长公共上升子序列一定是最长公共子序列中的一个上升子序列。
具体地,我们将数组a和b中的元素看作字符,将它们组成的序列看作字符串。对于a中的第i个元素和b中的第j个元素,如果它们相等,则它们一定是最长公共子序列中的一部分;否则,它们不可能同时出现在最长公共子序列中。因此,我们可以使用动态规划求解最长公共子序列问题。
定义dp[i][j]表示a中前i个元素和b中前j个元素的最长公共子序列长度。状态转移方程如下:
- 当a[i] == b[j]时,dp[i][j] = dp[i-1][j-1] + 1;
- 当a[i] != b[j]时,dp[i][j] = max(dp[i-1][j], dp[i][j-1])。
最终的答案即为dp[N][M]。
由于最长公共子序列问题的时间复杂度为O(NM),因此本问题的时间复杂度也为O(NM)。
相关问题
给定一个长度为 � N 数组 � a 和一个长度为 � M 的数组 � b。 请你求出它们的最长公共上升子序列长度为多少
我可以回答这个问题。最长公共上升子序列问题可以使用动态规划算法解决。具体来说,可以定义一个二维数组dp,其中dp[i][j]表示以a[i]和b[j]结尾的最长公共上升子序列长度。状态转移方程如下:如果a[i]和b[j]相等,则dp[i][j]=max(dp[k][l])+1,其中0<=k<i,0<=l<j且a[k]<a[i],b[l]<b[j];如果a[i]和b[j]不相等,则dp[i][j]=max(dp[k][j],dp[i][l]),其中0<=k<i且a[k]<a[i],0<=l<j且b[l]<b[j]。最终的最长公共上升子序列长度即为dp[N][M]。
给定一个长度为 n 的序列 {an},求其最长上升子序列长度。O(n logn)
可以使用二分查找和动态规划来解决这个问题,时间复杂度为 O(n logn)。
首先,我们定义一个数组 dp,其中 dp[i] 表示以第 i 个元素为结尾的最长上升子序列的长度。显然,dp[0] = 1。然后,我们从 i=1 开始遍历数组,对于每个 i,我们需要找到其中一个最大的 j,满足 a[j] < a[i] 且 dp[j] 是所有满足条件的 j 中最大的。然后,dp[i] 就等于 dp[j] + 1。
为了找到 j,我们可以使用二分查找来进行优化。具体来说,我们维护一个数组 b,其中 b[k] 表示长度为 k 的上升子序列中最后一个元素的最小值。我们从左到右遍历数组 a,对于每个 a[i],我们在 b 中查找第一个大于等于 a[i] 的元素 b[j],然后将 b[j] 更新为 a[i]。如果 b 中没有大于等于 a[i] 的元素,那么我们将 a[i] 加入到 b 的末尾。
最后,b 的长度就是最长上升子序列的长度。
以下是 Python 代码实现:
```python
def lengthOfLIS(nums):
n = len(nums)
dp = [1] * n
b = [float("inf")] * (n + 1)
b[0] = float("-inf")
for i in range(n):
# 二分查找
l, r = 0, i + 1
while l < r:
mid = (l + r) // 2
if b[mid] < nums[i]:
l = mid + 1
else:
r = mid
# 更新 b[j]
j = l
b[j] = nums[i]
# 更新 dp[i]
dp[i] = j
return max(dp)
```
时间复杂度为 O(n logn)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)