アルゴリズムライン

質問する

使用するライブラリ

bisect
整列配列で特定の要素を検索するには
bisect_left(a, x)
->リストaに挿入するxの一番左のインデックスで、ソート順を保持します

正解

import bisect
x = int(input())
arr = list(map(int, input().split()))
dp = [arr[0]]

for i in range(x):
    if arr[i] > dp[-1]:
        #오른쪽에서 왼쪽방향 -1
        dp.append(arr[i])
    else:
        idx = bisect.bisect_left(dp, arr[i])
        dp[idx] = arr[i]
print(len(dp))

説明:

arr[i]がdpの最後の要素(すなわち前の要素)より大きい場合
dp最後の位置に追加
arr[i]がdpの最後の要素より小さい場合
増分数列を有する貝列dpに入力する位置インデックス値をarr[i]で置き換える
dpの長さは,最も長く成長した部分数列の数である.

に質問

長さだけを求めて、要素を求めてはいけません
勉強の準備をしてアップロードします.

ポスト

アルゴリズムの流れは理解していますが.
問題の種類、実施に慣れていない
今でも答えを见て他人のコードを理解して勉强中...
ブログ参照