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

标签：

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

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Q.1.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.1.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)$ 时间算法的伪代码，求最长严格单调递增子序列的长度。

Kai

Q.1.1

Let $L[i,j]$ be the length of a longest common subsequence of prefixes $X[1..i]$ and $Y[1..j]$. Store one predecessor direction for reconstruction.

LCS(X[1..n], Y[1..n])
    for i = 0 to n
        L[i, 0] = 0
    for j = 0 to n
        L[0, j] = 0

    for i = 1 to n
        for j = 1 to n
            if X[i] = Y[j]
                L[i, j] = L[i-1, j-1] + 1
                P[i, j] = DIAGONAL
            else if L[i-1, j] >= L[i, j-1]
                L[i, j] = L[i-1, j]
                P[i, j] = UP
            else
                L[i, j] = L[i, j-1]
                P[i, j] = LEFT

    i = n; j = n; S = empty list
    while i > 0 and j > 0
        if P[i, j] = DIAGONAL
            prepend X[i] to S
            i = i - 1; j = j - 1
        else if P[i, j] = UP
            i = i - 1
        else
            j = j - 1
    return S

The recurrence is

$$L[i,j]= \begin{cases} L[i-1,j-1]+1,&X[i]=Y[j],\\ \max\{L[i-1,j],L[i,j-1]\},&X[i]\ne Y[j]. \end{cases}$$

There are $(n+1)^2$ table entries, each computed in constant time; reconstruction takes $O(n)$. Thus the running time is $O(n^2)$ and the space usage is $O(n^2)$.

Q.1.2

Maintain tail[l], the smallest possible final value of an increasing subsequence of length $l$ found so far.

LIS-LENGTH(A[1..n])
    length = 0
    for i = 1 to n
        l = LOWER-BOUND(tail[1..length], A[i])
            // first index l with tail[l] >= A[i]
        if no such index exists
            length = length + 1
            tail[length] = A[i]
        else
            tail[l] = A[i]
    return length

Replacing tail[l] by a smaller value preserves an extendable subsequence of length $l$; appending beyond the current last tail increases the optimum length by one. Therefore, after every iteration, length equals the longest increasing-subsequence length of the processed prefix. Each lower-bound search costs $O(\log n)$, so the total time is

$$\boxed{O(n\log n)}$$

with $O(n)$ space.