百題解答11053成長最長の部分数列

boj 11053:成長が最も長い部分数列
質問アドレス:https://www.acmicpc.net/problem/11053
難易度:silver 2
1.問題の説明

成長が最も長い部分数列の長さ

を探しています.
2.問題を解決する考え.

次元グリッド(テーブル)を作成し、

を解く

cache[i]=i第1の要素が有する最長増分部分数列長

.

冗長for文で、ピボットの前の値よりもピボットの値が大きい場合、

点火式により付与される.

3.問題の処理方法
次はコアコードです

for i in range(1,N): # 피벗 설정
    for j in range(i): # 피벗 이전의 숫자들을 순회하면서
        if numbers[j] < numbers[i]: # 피벗과 크기 비교
            cache[i] = max(cache[i], cache[j]+1) 

4.特別注意事項

いいえ、

時間複雑度O(N^2)

5.コード実装

N = int(input())
numbers = list(map(int, input().split()))
cache = [1] * (N)

for i in range(1,N):
    for j in range(i):
        if numbers[j] < numbers[i]:
            cache[i] = max(cache[i], cache[j]+1)

print(max(cache))