BOJ 12015:最長成長部分数列2

6908 ワード
boj テキストリンク

ソース:https://www.acmicpc.net/problem/12015


質問する


数列Aが与えられると、最も長い部分の数列を求めるプログラムが作成される.
例えば、A={10,20,10,30,20,50}を数える場合、最も長くなる部分はA={10,20,10,30,20,50}であり、長さは4である.

入力


第1行は、数列AのサイズN(1≦N≦1000000)を与える.
2行目は、数列Aを構成するAiを与える.(1 ≤ Ai ≤ 1,000,000)

しゅつりょく


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

アイデア


カウントが一番前(0番インデックス)より大きい数値です.(wrong)

コード#コード#


Mine (Wrong)

import sys
input = lambda : sys.stdin.readline()

N = int(input()) #수열의 길이
A = list(map(int, input().split())) #수열
temp = 0 #현재까지 탐색된 최대 숫자값
ans = 0

for i in range(N):
    if temp < A[i]:
        ans += 1
        temp = A[i]
print(ans)

改善


前の(0番のインデックス)が大きい場合、0番のインデックスを含む部分の列は最大長ではありません.
ex) 50, 10, 20, 30, 40, 60
code -> [50, 60]
ans -> [10, 20, 30, 40, 60]
考え方

Mine

import sys
from bisect import bisect_left

input = sys.stdin.readline

N = int(input()) #수열의 길이
A = list(map(int, input().split())) #수열
lis = [] #부분 수열

for num in A:
    if not lis: # 초기 값 넣어주기
        lis.append(num)
        continue
    if lis[-1] < num: # lis의 마지막(최대값)과 새로운 값 비교
        lis.append(num)
    else:
        index = bisect_left(lis, num)
        lis[index] = num

print(len(lis))
クリエイティブソース:https://velog.io/@uoayop/BOJ-12015-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%EC%A6%9D%EA%B0%80%ED%95%98%EB%8A%94-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4-2-Python

改善


対分用法-https://programming119.tistory.com/196


阿里雲RDSデータベース復旧ツールPercona XtraBackup実戦心得(心が痛くて涙が出る)
パーティション表部分パーティションデータのエクスポート