京都大学 情報学研究科 知能情報学専攻 2019年2月実施 専門科目 F1-1

标签：

• Kyoto-University
• Longest-Common-Subsequence
• Longest-Increasing-Subsequence

Author

itsuitsuki

Description

Q.1

Given two sequences of length $n$, write pseudocode of an $O(n^2)$-time algorithm to find a longest common subsequence. Note that a subsequence does not necessarily have to be contiguous. For example, if $X = (A, B, C, B, D, A, B)$ and $Y = (B, D, C, A, B, A, B)$, the sequence $(B, C, A)$ is a common (but not longest) subsequence of $X$ and $Y$.

Q.2

Given a sequence of permuted integers from 1 to $n$, write pseudocode of an $O(n \log n)$-time algorithm to find the length of the longest monotonically increasing subsequence.

题目描述

1. 给定两个长度均为 $n$ 的序列，写出一个 $O(n^2)$ 时间算法的伪代码，求一个最长公共子序列。子序列不要求连续；例如 $X=(A,B,C,B,D,A,B)$、 $Y=(B,D,C,A,B,A,B)$ 时，$(B,C,A)$ 是公共子序列，但不是最长者。
2. 给定由整数 $1,\ldots,n$ 的一个排列构成的序列，写出一个 $O(n\log n)$ 时间算法的伪代码，求最长严格单调递增子序列的长度。

考点

• 最长公共子序列动态规划：以两个前缀为状态，根据末元素是否相等建立二维递推，并恢复一个最优子序列。
• 最长递增子序列：维护各长度递增子序列的最小末尾值，并用二分查找将复杂度降为 $O(n\log n)$。

Kai