[백준11055_자바스크립트(javascript)] - 가장 큰 증가하는 부분 수열

🔴 문제

가장 큰 증가하는 부분 수열

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, inputs] = fs.readFileSync(path).toString().trim().split('\r\n');
const A = inputs.split(' ').map(Number);
const dp = inputs.split(' ').map(Number);

for (let i = 1; i < Number(n); i++) {
  for (let j = 0; j < i; j++) {
    if (A[i] > A[j]) {
      dp[i] = Math.max(dp[i], dp[j] + A[i]);
    }
  }
}

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

🟢 풀이

⏰ 소요한 시간 : 6분(복습)

LIS 알고리즘의 기본 유형. LIS를 학습하자 마자 풀어서 되게 조금걸렸다.
dp 배열은 i번째 요소는 i번째 요소를 마지막 원소로 하는 부분 수열의 합 중 최댓값을 정의한다. 따라서 dp 배열의 초기 값은 입력 값으로 설정해준다.
이후 값을 이중으로 순회하면서 비교 요소 A[j]보다 현재 타겟요소 A[i]가 더 클 경우 dp[i]의 부분 수열의 합 중 비교요소의 최댓값에 마지막 요소로 나를 더한 값과 현재 내가 가지고 있는 dp[i]의 값 중 최대값을 선택해주면 된다.

🔵 Ref

[백준11053_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열