[伯俊]11053号最長の部分数列増加-Phython


質問する


数列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)

しゅつりょく


第1行出力数列Aの最長増分部分数列の長さ.

I/O例



解答方法

import sys

N = int(sys.stdin.readline())
A = list(map(int, input().split()))
dp = [1] * N

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

print(max(dp))
  • 変数Aにリスト格納数列
  • 変数dpメモリリスト繰返し回数
  • Aアレイのif A[i] > A[j]が真の場合、dp[i] = max(dp[i], dp[j]+1)
  • A[i]未満の位置でdpテーブル値を最大値に変更すると
  • となります.
    伯準11053号:成長が最も長い部分数列