[Baekjoon] 11053. 最大増加分のカウント[2]

📚 質問する
https://www.acmicpc.net/problem/11053
最も長く成長した部分数列はDP Wellの既知の問題である.
nは1000で,forゲートを2回回転でき,完全にナビゲーションにより解決できる.
最初のインデックスから入力した数列をチェックし、コメントシーケンスに挿入します.
部分数列の最小長は自分の1なので、1でコメントを初期化します.
例として比較します.

Input

6
10 20 10 30 20 50
まずdpを1に初期化する.
Index012345arr102010302050dp111111
Index 1から以前の値があり、Index 1から検証を開始します.
Index 0の配列値はIndex 1より小さいので、Index 0のdp値に1を加算します.
Index012345arr102010302050dp121111
Index 2は以前の値ではより小さい値はないのでdpは1である.
Index012345arr102010302050dp121111
Index 3以前の値はすべて小さいです.従って、dp値が最大のIndex 1のdp値2に1を加算する.
Index012345arr102010302050dp121311
Index 4未満のIndexは0と2です.したがって,両方ともdpが1であり,さらに1または2を加える.
Index012345arr102010302050dp121321
Index 5のすべての数字は小さいです.従って、dp値が最大のIndex 3のdp値3に1を加算する.
Index012345arr102010302050dp121324
以下のdp値のうちの最値を出力します.
📒 コード#コード#

n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(n)]

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

🔍 結果