BOJ 11054 가장 긴 바이토닉 부분 수열 (JS)

 

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

11054번: 가장 긴 바이토닉 부분 수열

 

어려워서 구글링을 통해서 해결하였다.

 

핵심 아이디어는 다음과 같다.

 

왼쪽에서 증가하는 증가 부분 수열을 담은 dp배열과 오른쪽에서 감소하는 감소 부분 수열을 담은 dp2배열의 각 인덱스에서의 합들 중 최댓값을 구하고 1을 빼면된다.

1을 빼는 이유는 기준이 되는 값이 두번 계산이 되기 때문이다.

 

입력값이 만약

1 5 2 1 4 3 4 5 2 1

일 경우,

 

dp 배열 => 1 2 2 1 3 3 4 5 2 1

dp2 배열 => 1 5 2 1 4 3 3 3 2 1

이고,

dp+dp2 배열 => 2 7 4 2 7 6 7 8 4 2

이므로, 8-1 = 7 해서 답은 7이 된다.

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const n = Number(input.shift());
const arr = input[0].split(' ').map(Number);
const dp = Array(n).fill(1);
const dp2 = Array(n).fill(1);

// 10
// 1 5 2 1 4 3 4 5 2 1

for (let i = 0; i < n - 1; i++) {
  for (let target = i + 1; target < n; target++) {
    if (arr[i] < arr[target]) {
      dp[target] = Math.max(dp[i] + 1, dp[target]);
    }
  }
}

for (let i = n-1; i >0; i--) {
    for (let target = i-1; target>=0; target--) {
      if (arr[i] < arr[target]) {
        dp2[target] = Math.max(dp2[i] + 1, dp2[target]);
    }
}
}

const answer=[];
for(let i=0; i<n; i++){
    answer.push(Math.max(dp[i]+dp2[i]-1));
}

console.log(Math.max(...answer))