[Node.js] 11053_가장 긴 증가하는 부분 수열

문제

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

 

 

풀이

이 문제는 LIS 알고리즘과 DP 알고리즘을 이용한 문제이다.

 

DP 알고리즘을 이용해 지금까지 증가한 연속된 부분 수열의 개수를 저장해 사용한다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n] = input.shift();
const arr = input.shift();
const temp = Array.from({ length: n }, () => 1);

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

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