白駿11053号「最も成長した部分数列」

質問する

百準11053回成長最長の部分数列

に答える

'LIS'
動的計画法で解く.
列を順番に繰り返すには、現在の順序の数字を前の数字と比較して、現在の数字のk値(現在の数字が部分列に入ったときの順序)を変更します.
ex)arr=[10,20,10,30,20,50]の場合
i値が増加すると、k配列は次のようになります.

Pythonコード

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
k = [1]*n

for i in range(1, n):
    for j in range(i):
        if arr[j] < arr[i]:
            k[i] = max(k[i], k[j]+1)

print(max(k))