给定一个长度为N 数组a 和一个长度为M 的数组b。 请你求出它们的最长公共上升子序列长度为多少。

首先，我们可以将问题转化为最长公共子序列（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的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱） 例如：给定一个长度为8的数组A{1，3，5，2，4，6，7，8}，则其最长的单调递增子序列为{1，2，4，6，7，8}，长度为6。 输入：数组，数组长度 输出：输出该数组最长递增子序列的长度

这个问题可以使用动态规划（Dynamic Programming）中的滑动窗口（Sliding Window）算法来解决。首先，创建两个变量，end记录当前找到的最长递增子序列的结尾位置，length存储最长递增子序列的长度。
初始化 end = 0 和 length = 1（因为第一个元素本身就是单个递增子序列）。接下来，遍历数组从索引1开始：

检查 arr[end] < arr[i]，如果满足条件（即当前元素大于前一个子序列的最后一个元素），说明找到了一个新的递增子序列的起点，将 end 更新为 i，并将 length 加一。
如果 arr[end] >= arr[i]，说明当前位置无法延长递增子序列，需要回溯到下一个可能的位置，这时更新 end 为 i - 1，并检查 arr[end + 1] 是否能继续增加，若能，则更新 end。

遍历结束后，length 就是所求的最长递增子序列的长度。
下面是一个伪代码示例：
function findLongestMonotonicSubsequence(arr):
length = 1
end = 0

for i in range(1, len(arr)):
if arr[end] < arr[i]:
length += 1
end = i
else:
while (end > 0 and arr[end] >= arr[i]):
end -= 1
end += 1

return length