가장 쉽게 푸는 방법은 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 주어진 수열의 정방향과 역방향으로 적용해주면 해결 가능합니다.
주어진 예제를 봅시다.
1 5 2 1 4 3 4 5 2 1
위 수열에서 정방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을 때 결과는 아래와 같습니다.
가장 긴 수열이 어떤 부분 수열인지는 상관없습니다.
[1, 2, 2, 1, 3, 3, 4, 5, 2, 1]
다음으로 역방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을 때 결과는 아래와 같습니다.
가장 긴 수열이 어떤 부분 수열인지는 상관없습니다.
[1, 5, 2, 1, 4, 3, 3, 3, 2, 1]
이제 이 두 테이블을 비교하면서 각 인덱스에 위치한 값의 합이 가장 큰 경우를 찾으면 됩니다.
두 테이블의 원소를 서로 합하면 아래와 같습니다.
[2, 7, 4, 2, 7, 6, 7, 8, 4, 2]
여기서 가장 합이 큰 경우는 8입니다. 단 두 테이블이 원본 배열에서 원소 5를 중복 체크하고 있기에 8에서 1을 뺀 결괏값 7을 정답으로 도출할 수 있습니다.
작성 코드 (Python)
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
table_a, table_b = [1] * n, [1] * n
for i in range(n):
for j in range(i):
if arr[i] > arr[j]:
table_a[i] = max(table_a[i], table_a[j] + 1)
for i in range(n - 1, -1, -1):
for j in range(n - 1, i, -1):
if arr[i] > arr[j]:
table_b[i] = max(table_b[i], table_b[j] + 1)
result = 0
for i in range(n):
result = max(result, table_a[i] + table_b[i] - 1)
print(result)
작성 코드 (JavaScript)
function solution(n, array) {
const [tableA, tableB] = [Array(n).fill(1), Array(n).fill(1)];
for (let i = 0; i < n; i += 1) {
for (let j = 0; j < i; j += 1) {
if (array[i] > array[j]) tableA[i] = Math.max(tableA[i], tableA[j] + 1);
}
}
for (let i = n - 1; i >= 0; i -= 1) {
for (let j = n - 1; j > i; j -= 1) {
if (array[i] > array[j]) tableB[i] = Math.max(tableB[i], tableB[j] + 1);
}
}
let result = 0;
for (let i = 0; i < n; i += 1) {
result = Math.max(result, tableA[i] + tableB[i] - 1);
}
return result;
}
solution(10, [1, 5, 2, 1, 4, 3, 4, 5, 2, 1]);