[node.js] 가장 긴 증가하는 부분 수열 ( 백준 11053번 )

나는 이걸 틀려서, 결국 다른 사람의 코드를 참고했었다. 유명한 알고리즘이라 별도의 이름도 있다고 한다.
LIS 라고 하는데, 말 그대로 Longest Increase Sequence? 뭐 그런 이름이었던 거 같다.
나는 이걸 짜기 위해서 n이 증가함에 따라 이전에 가능했던 수열에 새 값을 붙인 경우, 붙이지 않은 경우를 탐색했는데,
메모리 초과가 심각해서 풀 수가 없었다.
DP는 DP 방법 말고는 답이 없는 듯 하다.

다음 문제가 가장 긴 감소하는 부분 수열인데,코드를 전혀 보지 않고 풀어보도록 하자.

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

let count = 0;

rl.on("line", (line) => {
    if (!count) {
        count = Number(line);
    } else {
        main(line);
        rl.close();
    }
}).on("close", () => {
    process.exit();
});

/**
 *
 * @param {string} line
 */
const main = (line) => {
    const numbers = ("0 " + line).split(" ").map(Number);
    const DP = new Array(count + 1).fill(1);

    for (let i = 2; i < DP.length; i++) {
        let temp = 0;
        for (let j = 1; j < i; j++) {
            if (numbers[j] < numbers[i]) {
                if (temp < DP[j] + 1) {
                    temp = DP[j] + 1;
                }
            }

            if (temp != 0) {
                DP[i] = temp;
            }
        }
    }

    console.log(Math.max(...DP));
};