# Problem

# A subsequence of a permutation is a collection of elements of the permutation in the order that they appear. For example, (5, 3, 4) is a subsequence of (5, 1, 3, 4, 2).

# A subsequence is increasing if the elements of the subsequence increase, and decreasing if the elements decrease. For example, given the permutation (8, 2, 1, 6, 5, 7, 4, 3, 9), an increasing subsequence is (2, 6, 7, 9), and a decreasing subsequence is (8, 6, 5, 4, 3). You may verify that these two subsequences are as long as possible.

# Given: A positive integer n≤10000 followed by a permutation π of length n.

# Return: A longest increasing subsequence of π, followed by a longest decreasing subsequence of π.

# Sample Dataset

# 5

# 5 1 4 2 3

# Sample Output

# 1 2 3

# 5 4 2

# 對(duì)于一個(gè)給定的長(zhǎng)度為 n 的排列 π，求它的最長(zhǎng)上升子序列和最長(zhǎng)下降子序列。

n =5

a = [5, 1, 4, 2, 3]

dp1 = [1] * n# 最長(zhǎng)上升子序列

pre1 = [-1] * n# 記錄前驅(qū)，方便輸出

for iin range(n):

for jin range(i):

if a[j] < a[i]:

if dp1[j] +1 > dp1[i]:

dp1[i] = dp1[j] +1

? ? ? ? ? ? ? ? pre1[i] = j

dp2 = [1] * n# 最長(zhǎng)下降子序列

pre2 = [-1] * n

for iin range(n):

for jin range(i):

if a[j] > a[i]:

if dp2[j] +1 > dp2[i]:

dp2[i] = dp2[j] +1

? ? ? ? ? ? ? ? pre2[i] = j

# 輸出最長(zhǎng)上升子序列

idx1 = dp1.index(max(dp1))

ans1 = []

while idx1 != -1:

ans1.append(a[idx1])

idx1 = pre1[idx1]

print(*ans1[::-1])# 注意倒序輸出

# 輸出最長(zhǎng)下降子序列

idx2 = dp2.index(max(dp2))

ans2 = []

while idx2 != -1:

ans2.append(a[idx2])

idx2 = pre2[idx2]

print(*ans2[::-1])