가장 긴 바이토닉 부분 수열

문제

백준 11054번 - 가장 긴 바이토닉 부분 수열

언어

JavaScript

문제 풀이 step 1

가장 긴 증가하는 부분수열과 가장 긴 감소하는 부분수열 구해서 그 둘을 합하는 방식으로 가장 긴 바이토닉 부분 수열을 구했습니다.
백준 11053번 - 가장 긴 증가하는 부분 수열 풀이
백준 11722번 - 가장 긴 감소하는 부분 수열 풀이
풀이는 위의 풀이 두개를 합친 것과 다름이 없어서 별다른 풀이는 적지 않겠습니다.

추가로 배운 점

자바스크립트의 Array의 reverse 메서드는 호출한 배열을 역순으로 뒤집고, 그 참조를 반환합니다.
즉, 역순으로 뒤집은 새로운 배열을 반환하는 것이 아닙니다.

소스 코드 1

// 반복 2번하는 풀이
const input = require("fs").readFileSync("/dev/stdin").toString().split("\n");

const getMaxLenIncreasingSubSequence = (numArr) => {
	const dp = [1];

	for (let i = 1; i < numArr.length; i++) {
		dp[i] = 1;
		for (let j = 0; j < i; j++) {
			if (numArr[j] < numArr[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
		}
	}

	return dp;
};

const solution = (input) => {
	const n = parseInt(input[0]);
	const numArr = input[1].split(" ").map(Number);

	// 가장 긴 증가하는 부분 수열
	const increasingDp = getMaxLenIncreasingSubSequence(numArr);
	// 가장 긴 감소하는 부분 수열
	const decreasingDP = getMaxLenIncreasingSubSequence(
		numArr.reverse()
	).reverse();

	let max = 0;
	for (let i = 0; i < n; i++) {
		const bitonicSubSequence = increasingDp[i] + decreasingDP[i] - 1;
		if (max < bitonicSubSequence) max = bitonicSubSequence;
	}

	return max;
};
console.log(solution(input));