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

백준 11054번

💊 증가수열DP와 감소수열DP를 각각 만든 후 합쳐주어야한다.
🧸 난 증가수열DP 만드는 방법도 잊고있었다..😥 이제는 꼭 기억해야지.

코드

const fs = require('fs'); 
let input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const N = +input.shift();
input = input[0].split(" ").map(Number);
let increaseDP = new Array(N).fill(1);
let decreaseDP = new Array(N).fill(1);
let dp = [];

for (let i = 1; i < N; i++) {
  let values = [1];
  for (let j = 0; j < i; j++) {
    if (input[j] < input[i]) {
      values.push(increaseDP[j] + 1);
    }
  }
  increaseDP[i] = Math.max(...values);
}

for (let i = N - 2; i >= 0; i--) {
  let values = [1];
  for (let j = N - 1; j > i; j--) {
    if (input[j] < input[i]) {
      values.push(decreaseDP[j] + 1);
    }
  }
  decreaseDP[i] = Math.max(...values);
}

for (let i = 0; i < N; i++) {
  dp[i] = increaseDP[i] + decreaseDP[i] - 1;
}

console.log(Math.max(...dp));