伯準11053号:成長が最も長い部分数列

3697 ワード
python ps DP テキストリンク
伯準11053号:成長が最も長い部分数列

アイデア


arr[i]が持つことができる最大長をd[i]に書き込む.最初のインデックスからi-1のインデックスに移動し、arr[i]値よりも長く、小さい要素を探します.

コード#コード#

N = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
d = [0]*(N + 1)

for i in range(1, N + 1):
    tmp = 0
    for j in range(i):
        if tmp < d[j] and arr[j] < arr[i]:
            tmp = d[j]
    d[i] = tmp + 1

print(max(d))

おしゃべり


このように解くと,時間的複雑度はO(N^2)である.この方法では,入力サイズ1000000の12015題を解決できない.君はほかの方法を考えなければならない.
[珂苔]14-1次元ダイナミック
[プログラマー]橋を渡る