https://www.acmicpc.net/problem/11054
11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net
엄청끙끙대다가 접근방식을 봤는데 생각보다 너무 간단했다.
수열 a의 모든 원소 i에 대해서,
a[i]까지의 증가하는 수열과a[j]까지의 감소하는 수열을 구한다.
이후 이 둘을 더하고 1을빼주면 된다.(a가 중복되므로)
나는 그냥 반복을 2번돌려서 풀었다.
증가하는 수열을 모두 구한 후에, 감소하는 수열을 모두 구했다.
n=int(input())a=[* map(int,input().split())]dp=[[1,1] for _ in range(n)]
for i in range(1,len(dp)): max_len=0 for j in range(i):
if a[j]<a[i]: max_len=max(max_len,dp[j][0])
dp[i][0]+=max_lenfor q in range(n-1,-1,-1): min_len=0
for k in range(n-1,q,-1): if a[q]>a[k]:
min_len=max(min_len,dp[k][1]) dp[q][1]+=min_lenanswer=1
for dd in dp: answer=max(answer,sum(dd))print(answer-1)정답을 훑어보는 도중, 반복문 한번으로 깔끔하게 처리하는 방식을 발견했다.
먼저 a를 뒤집은 b를 만들고,
한번 반복할때마다 a,b를 통해 dp_up,dp_down (i 까지의 증가수열, 감소수열) 을 업데이트한뒤
정답 answer[i]에
dp_up[i] 와 dp_down[n-i-1] (얘는 뒤집었으므로 원래위치는 n-i-1이 된다)
를 더한 값을 업데이트시켜주면 된다.
n=int(input())a=[* map(int,input().split())]b=a[::-1]dp_up=[1 for _ in range(n)]
dp_down=dp_up.copy()for i in range(n): for j in range(i):
if a[i]>a[j]: dp_up[i]=max(dp_up[i],dp_up[j]+1)
if b[i]>b[j]: dp_down[i]=max(dp_down[i],dp_down[j]+1)
answer=[dp_up[x]+dp_down[n-x-1] for x in range(n)]print(max(answer)-1)