문제

https://www.acmicpc.net/problem/11053

소스코드

import sys
input = sys.stdin.readline


if __name__ == "__main__":  
    n = int(input())
    arr = list(map(int,input().split()))
    dp = [0] * n

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

설명

• for i in range(n): for j in range(i):
  주어진 수열을 하나씩 선택해서 선택한 수열 밑에 값이 작은게 몇개나 있는지 체크한다.

• if arr[i] > arr[j] and dp[j] > dp[i]
  선택한 수열의 값이 무조건 커야하고 & 조건으로 누적된 값이 현재 체크하는 수열 값의 누적값 (dp[i]) 보다 크면 그 값을 채택한다. (꾸준히 증가했다는 뜻임)

• dp[i]+=1
  나 자신을 포함해야하므로 1을 무조건 더해준다. (감소하는 수열이면 dp[i]는 1이 된다.)