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

3879 ワード
テキストリンク
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))
    [伯俊]5622番ダイヤル-JAVA
    🔥 TIL - Day 41