[백준] 11054 가장 긴 바이토닉 부분 수열 - javascript

📌 문제

https://www.acmicpc.net/problem/11054

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +input[0];
const nums = input[1].split(" ").map(Number);

const increaseDP = new Array(n).fill(1);
const decreaseDP = new Array(n).fill(1);

// 증가 DP 구하기
for (let i = 0; i < n; i++) {
  const cur = nums[i];
  let cnt = 1;
  for (let j = 0; j < i; j++) {
    const compare = nums[j];
    if (cur > compare) cnt = Math.max(cnt, increaseDP[j] + 1);
  }
  increaseDP[i] = cnt;
}

// 감소 DP 구하기
for (let i = n - 1; i >= 0; i--) {
  const cur = nums[i];
  let cnt = 1;
  for (let j = i + 1; j < n; j++) {
    const compare = nums[j];
    if (cur > compare) cnt = Math.max(cnt, decreaseDP[j] + 1);
  }
  decreaseDP[i] = cnt;
}

console.log(
  Math.max(...increaseDP.map((incVal, index) => incVal + decreaseDP[index])) - 1
);

✔ 알고리즘 : DP

✔ 구해야 하는 최대길이의 바이토닉 수열을 구하려면 처음부터 현재 index까지의 증가수열의 길이와 현재 index부터 마지막까지의 감소수열의 길이를 알아야 한다.

✔ 증가수열의 DP
현재 index와 이전의 index를 비교하면서 현재 index의 값이 비교하는 index의 값보다 큰 경우 현재 cnt값과 비교 index의 increaseDP + 1과 비교하여 큰 값을 cnt로 갱신

✔ 감소수열의 DP
현재 index와 이후의 index를 비교하면서 현재 index의 값이 비교하는 index의 값보다 큰 경우 현재 cnt값과 비교 index의 decreaseDP + 1과 비교하여 큰 값을 cnt로 갱신

✔ increaseDP[i] + decreaseDP[i] 의 최댓값을 구한다.

✔ 최댓값에서 -1한 값이 가장 긴 바이토닉 부분 수열이다.

✔ 난이도 : 백준 기준 골드 3