https://www.acmicpc.net/problem/11053
11053번: 가장 긴 증가하는 부분 수열
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
www.acmicpc.net
n = int(input())
arr = list(map(int, input().split(' ')))
dp = [1] * n
for i in range(1, n):
for j in range(0, i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))
'알고리즘 > 백준 (Pyhthon)' 카테고리의 다른 글
| [알고리즘] 백준 17269 이름궁합 테스트 / python (0) | 2020.02.24 |
|---|---|
| [알고리즘] 백준 9251 LCS / python (0) | 2020.02.12 |
| [알고리즘] 백준 12865 평범한 배낭 / python (0) | 2020.02.11 |
| [알고리즘] 백준 1904 01타일 / python (0) | 2020.02.09 |
| [알고리즘] 백준 1766 문제집 / 위상정렬, python (0) | 2020.02.09 |
