풀이 코드

이것은 가장 긴 증가하는 부분 수열 알고리즘이다.
옛날에 백준에서 풀었던 문제와 매우 흡사해서 빠르게 풀이했다.
풀이 방법은 dp와 이분탐색이 있다.
LIS(Longest Increasing Subsequence) 이라고 하는데, 굳이 작성하지 않겠다.
내가 푼 풀이는 dp로 풀었는데 2중 루프를 돌면서 현재 위치에 있는 돌을 기준으로 서쪽에 있는 돌들과 비교해서 크면 그 돌이 전에 얼마만큼의 긴 수열을 가졌는지 작성된 값에 +1과 현재 돌의 작성된 긴 수열 값과 비교해서 큰 값을 업데이트 시켜주는 방식이다.

풀이 방법

import sys

n = int(sys.stdin.readline())

arr = list(map(int, sys.stdin.readline().split()))

dp = [1 for i in range(n)]

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

print(max(dp))