[알고리즘-JS] 동적 계획법 - 최대 부분 증가 수열

문제

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

 

입력 예제

5 3 7 8 6 2 9 4

 

출력 예제

4

 

 

 

 

풀이

function solution(arr){  
  let answer = 0;
  let dy = Array.from({length: arr.length}, () => 0);
  // 앞에 다른 수가 없으니 자기 자신 1로 초기화
  dy[0] = 1;
  
  for (let i = 1; i < arr.length; i++) {
    let max = 0;
    // i번째 요소의 앞 요소들을 순회
    for (let j = i - 1; j >= 0; j--) {
      // 증가 수열 가능하고 해당 dy 값이 max보다 크다면 
      if (arr[j] < arr[i] && dy[j] > max) {
        max = dy[j];
      }
    }
    dy[i] = max + 1; // 자기 자신 1을 더한다.
    answer = Math.max(answer, dy[i]);
  }

  return answer;
}