[백준] 가장 긴 증가하는 부분 수열 11053 (파이썬)

스케치

코드

x = int(input())
arr = list(map(int, input().split()))

# 먼저 배열과 같은 크기를 같는 1로 가득찬 배열을 하나 만들어준다. ex) r=6, res={1,1,1,1,1,1}
dp = [1 for _ in range(x)] # 길이가 가장 긴 /증가하는부분수열의 길이

for i in range(x): i = 2
    # 해당 로직은 오름차순 정렬에 대해 생각해야 수월하다 오름차순 정렬을 하려면
    # 자신보다 왼쪽에 있는 숫자가 자신보다 작아야 오름차순 정렬이다. ex) 2를 기준으로 1,2 => 오름차순O / 2,2 => 오름차순x
    # 2번째 자리보다 작은 숫자가 있어야하는것은 1번째 자리이다. ex) 3번째 자리면 우리는 1부터 3까지의 자리만 비교해주면 된다.
    for j in range(i):
        if arr[i] > arr[j]:
            
            # 하나씩 비교해서 큰게 맞으면 res[i]와 res[j] + 1 중에 큰값을 res[i] 담아준다
            # 이 숫자는 해당 인덱스 번호의 숫자가 가질수 있는 오름차순 정렬 배열 길이 이다 모든 숫자는 자기자신의 오름차순 정렬을 가질수 있기때문에 res={1,1,1,1,1,1}를 해준것!
            # 이말은 숫자를 누적해주기 위함과 바로 왼쪽의 숫자가 자신보다 작은데 가지고 있는 오름차순 정렬 길이가 3이라면 그것보다 큰수인 자신은 당연히 +1개
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp)) # 그중 제일 큰것 = 제일 긴 오름차순 길이