[python]バックアップ/最大成長部分数列/1053回/LIS,DP

DPコンセプトショートカット
質問する
最も長いローカル数列問題リンク
数列Aが与えられると、最も長い部分の数列を求めるプログラムが作成される.
例えば、A={10,20,10,30,20,50}を数える場合、最も長くなる部分はA={10,20,10,30,20,50}であり、長さは4である.
入力
第1行は、数列AのサイズN(1≦N≦1000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000)

6
10 20 10 30 20 50

しゅつりょく
第1行出力数列Aの最長増分部分数列の長さ.

4

方法

dpテーブルを生成して1に初期化

複文で数列を最初からチェックする

現在の数と以前の数を比較する

現在数が前の数より大きい場合は、前の数のdp値に1を加算し、現在のdp値に比べて大きな値を現在のdpに入れる

dp値は、現在のカウントが終了した部分カウントㅇの最大長である.

コード#コード#

# LIS 문제라고도 부른다 Longest Increase Subsequence

# DP 풀이

n = int(input())
num_list = list(map(int,input().split()))

dp = [1] * n

for i in range(1, n):
    for j in range(i):
        if num_list[i] >num_list[j]:
            dp[i] = max(dp[j]+1, dp[i])


print(max(dp))