[알고리즘/인프런] 최대 부분 증가수열(LIS, dp)

문제

---

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

 

풀이

---

function solution(arr) {
  const n = arr.length;
  let dy = Array.from({ length: n }, () => 0);
  dy[0] = 1;

  for (let i = 1; i < n; i++) {
    // 현재까지의 최장 증가 수열 길이는 현재 원소보다 앞에 위치한 작은 수 중 dy 값이 가장 큰 요소에서 1 증가
    for (let j = 0; j < i; j++) {
      if (arr[j] < arr[i]) dy[i] = Math.max(dy[i], dy[j] + 1);
    }
  }
  return Math.max(...dy);
}

연속적인 증가하는 수열이 아니기 때문에 dp가 필요하다.

 

첫 번째 반복문을 배열 전체를 순회한다. 두 번째 for문은 현재 원소 앞쪽만 순회하면서 마찬가지로

현재 원소보다 작은 값들 중 dy 값이 최댓갑인 원소를 찾아서 dy[i]에 저장한다.