[알고리즘] 가장 긴 바이토닉 부분 수열

구현 방식

• 동적 계획법으로 진행한다.
• acc는 이중 배열로 아래와 같이 표현할 수 있다.
  • 0 번째 행 : 현재 탐색하고 있는 숫자를 포함한 오름차순 최대 길이
  • 1 번째 행 : 현재 탐색하고 있는 숫자가 내림 차순의 시작점 또는 오른 후 내려가고 있는 나열의 최대 길이
• 0 번째 행은 이전에 구했던것처럼 이전 탐색한 숫자들의 오름차순 최대 길이 중에서 현재 탐색하고 있는 숫자 보다 작은 것 중 최대 길이에 해당 하는 값에 1을 더한 값에 해당한다.

acc[0][k] = max(acc[0][k], acc[0][i] + 1) , 0 <= i < k && numbers[i] < numbers[k]

• 1 번째 행은 현재 탐색하고 있는 숫자의 오름 차순 최대 길이(내림 차순의 시작점) 또는 이전에 오르내림차순 으로 탐색 했던 1번째 행 중에 현재 탐색하고 있는 숫자보다 큰 값 중 최대 길이에 해당 하는 값에 1 을 더한 값에 해당한다.

acc[0][k] = max(acc[1][k], acc[0][k])
acc[0][k] = max(acc[1][k], acc[1][i] + 1) , 0 <= i < k && numbers[k] < numbers[i]

• 입출력 예제를 사진으로 나타내면 아래와 같다.

코드

• 최종 코드는 아래와 같다.

void solution(int N)
{
	dp(N);
	int result = INT_MIN;
	for (int i = 0; i < N; i++)
		result = max(result, acc[1][i]);

	cout << result;
}

void dp(int N)
{
	acc[0][0] = acc[0][1] = 1;
	for (int i = 1; i < N; i++)
	{
		// 오름 차순
		for (int j = 0; j < i; j++)
		{
			if (numbers[j] < numbers[i])
				acc[0][i] = max(acc[0][j] + 1, acc[0][i]);
		}

		acc[1][i] = max(acc[0][i], acc[1][i]);


		// 내림 차순 허용
		for (int j = 0; j < i; j++)
		{
			if (numbers[i] < numbers[j])
				acc[1][i] = max(acc[1][j] + 1, acc[1][i]);
		}
	}
}