n = int(input())
a = list(map(int, input().split()))
d1 = [1] * n
d2 = [1] * n
for k in range(n):
for j in range(k):
if a[j] < a[k] and d1[k] < d1[j] + 1:
d1[k] = d1[j] + 1
for k in range(n-1, -1, -1):
for j in range(k+1, n):
if a[j] < a[k] and d2[k] < d2[j] + 1:
d2[k] = d2[j] + 1
ans = 0
for i in range(n):
ans = max(ans, d1[i] + d2[i]-1)
print(ans)
- 앞에서부터 증가하는 가장 긴 수열 2. 뒤에서부터 증가하는 가장 긴 수열
두가지 배열을 만들어서 브루트포스로 각 인덱스를 기준으로 두 값의 합이 가장 큰거 구함
(인덱스까지 증가 + 감소 = 바이토닉)
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
d1 = [1] * n
d2 = [1] * n
for k in range(i+1):
for j in range(k):
if a[j] < a[k] and d1[k] < d1[j] + 1:
d1[k] = d1[j] + 1
for k in range(i+1, n):
for j in range(i+1, k):
if a[j] > a[k] and d2[k] < d2[j] + 1:
d2[k] = d2[j] + 1
ans= max(max(d1) + max(d2), ans)
print(ans)
처음에는 인덱스 기준 앞은 증가하는, 뒤는 감소하는 가장 긴 수열을 인덱스마다 계산해서 3중 for문을 돌리려했어서 시간 초과가 남