✓

태그:

14. 동적 계획법 1 CLASS 4

가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다. 11053번: 가장 긴 증가하는 부분 수열을 응용하는 문제입니다. 바이토닉 수열의 정의에 따르면 특정 점을 기준으로 양쪽으로 감소하는 수열이면 됩니다. 이 수열을 특정 점을 기준으로 잘라보면 왼편은 순방향의 LIS, 오른편은 역방향의 LIS입니다. 즉, 배열의 각 원소에 대해 해당 원소를 마지막으로 하는 순방향 LIS와 역방향 LIS의 길이를 모두 구한 뒤, 순방향 LIS와 역방향 LIS의 길이의 합이 가장 큰 원소를 찾으면 됩니다. 이를 찾은 뒤, 두 LIS의 길이의 합에서 1을 빼면 바이토닉 부분 수열의 길이가 나옵니다.

소스 코드

언어	코드	시간
C++	코드(Github) / 코드(백준)	2020-04-01 00:24:14

---