[알고리즘][dynamic programing] 최대 부분 증가수열

문제

N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.
▣ 입력설명
첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
8 53786294
▣ 출력예제 1
4

풀이

처음에 어떻게 해야할지 감이 안 잡혔다...
부분 증가수열이라는 이름 부터 너무 오랜만이라 생소했다.

function solution(length, numbers) {
const dy = Array.from({length: length}, () => 0)
let max = 0;
let answer = 0;
  for(let i=0; i<length; i++) {
    for(let j=i-1; j>=0; j--) {
      if(numbers[j]<numbers[i] && dy[j] > max) {
        max = dy[j]
      }
    }
    dy[i] = max + 1;
    answer = Math.max(answer, dy[i])
  }
  return answer;
}