- 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
n = int(input())
ls = list(map(int, input().split()))
dyn = [0]*n
dyn[0] = 1
for i in range(1, n):
length = 1
for j in range(0, i):
if ls[j] < ls[i]:
if length <= dyn[j]:
length = dyn[j]+1
dyn[i] = length
print(max(dyn))
|
cs |
같은 방식의 다른 응용 문제
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
n = int(input())
arr = list(map(int, input().split()))
length = [0]*n
length[0] = 1
res = -2147000000
for i in range(1, n):
max = 0
for j in range(0, i):
if arr[i] > arr[j] and length[j] > max:
max = length[j]
length[i] = max + 1
if length[i] > res:
res = length[i]
print(res)
|
cs |
728x90