[JavaScript/section 10] 03 - 최대 부분 증가 수열

📌 최대 부분 증가수열(LIS)

N개의 자연수로 이루어진 수열이 주어졌을 때, 그중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 문제이다. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길이가 5인 최대 부분 증가 수열을 만들 수 있다.

 

입력설명

첫째 줄은 입력되는 데이터의 수 N(1<=N<=1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.

둘째 줄은 N개의 입력데이터들이 주어진다.

출력설명

첫 번째 줄에 부분 증가 수열의 최대 길이를 출력한다.

입력예제	출력예제
8 5 3 7 8 6 2 9 4	4

 

📝 풀이 방법

arr[ i ](인덱스) - 증가 수열에서 마지막 항에 해당하는 숫자

dy[ i ] - arr[ i ] (i 번째 원소)가 수열의 마지막 항에 해당한다는 조건하에 부분 증가 수열의 길이

답을 찾아가는 과정의 한 부분~

• arr[3]에 해당하는 원소 8이 증가 수열의 마지막 항에 해당하는 숫자로 앞에 존재하는 원소들과 비교한다.
• 앞에 존재하는 원소 중 arr[3]보다 작으면서 부분 증가 수열의 길이가 가장 긴 길이에 1(자기 자신 포함)을 더한 값을 dy[3]에 저장한다.
• 위 과정을 반복한 후 dy 배열의 원소 중 최대 길이를 구한다.

function solution(arr) {
  let answer = 0;
  let dy = Array.from({ length: arr.length }, () => 0);
  // arr[0] 앞에 원소가 존재하지 않기 때문에 증가 수열에 자기 자신만 포함하므로 1로 초기화
  dy[0] = 1;

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

  answer = Math.max(...dy);
  return answer;
}

let arr = [2, 7, 5, 8, 6, 4, 7, 12, 3];
console.log(solution(arr));