[알고리즘] 가장 긴 증가하는 바이토닉 부분 수열 (DP-Gold IV)

목적 :

다른사람의 매우 직관적인 풀이를 복습하기 위해서

​

문제 설명(요약) :

증가 or 감소 , 증가+감소, 감소+증가 의 특징을 가진 바이토닉 수열 중에서 가장 긴 수열을

찾아 길이를 구하면 되는 문제

​

나의 시도 :

1. 가장 긴 증가 or 감소 수열에서 기울기 부호가 바뀌는 지점의 인덱스를 구해 그 후 가장 긴 반대 수열 길이 더하기

​

깨달은 것:

가장 긴 증가 수열이 아니더라도 가장 긴 바이토닉 수열이 될 수있다.

반대의 경우도 마찬가지

​

해결 전략:

dp 배열에는 해당 인덱스 값마다 최대 길이가 들어있으므로

해당 시점에서의 증가수열길이 + 감소수열길이 -1 을 해주면 된다.

단 감소 수열은 top-down 방식으로 증가 수열의 길이를 할당 해줘야

겹치는 부분에서 길이 합을 구할 때 제대로 계산이 될 수 있다.

(dp 배열에 해당 인덱스 값이 들어있는걸 잊고 풀어서 시간이 꽤 걸렸다.)