最大ローカル増分数列

4077 ワード
python アルゴリズム#アルゴリズム# テキストリンク
作成日:2022年2月23日午後5:09

インプリメンテーションコード

# 최대 부분 증가수열
import sys
sys.stdin = open("input.txt", "rt")

n = int(input())
arr = list(map(int, input().split()))
arr.insert(0, 0)
dy = [0] * (n+1)

dy[1] = 1

for i in range(2, n+1):
    maxLen = 0
    for j in range(1, i):
        if arr[i] > arr[j]:
            if dy[j] > maxLen:
                maxLen = dy[j]
    dy[i] = maxLen+1

print(dy)
  • iの第1の値位置では、最長の数列は第1の値から始まり、i−1の値(j)の中でiより小さく、最も長い値を探し、その値の中の数列の最大長に1を加算する.
    • 最大線の接続
    石橋を跨ぐ(Bottom-UP)