IF - LIS

문제

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

예시

Input	Output
[5, 3, 7, 8, 6, 2, 9, 4]	4
[2, 7, 5, 8, 6, 4, 7, 12, 3]	5

풀이 및 회고

• 주어진 배열만큼의 길이를 갖는 빈 배열 dy 를 만들고 0 으로 초기화한다.
• dy의 각 원소는 arr의 동일 인덱스의 원소가 수열의 마지막 수라고 가정했을 때의 수열의 길이이다.
• 다이나믹 프로그래밍이라는 새로운 알고리즘을 배울 수 있어서 좋았다.

코드

const solution = (arr) => {
	const dy = Array.from({ length: arr.length }, () => 0);

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

	const answer = Math.max(...dy);
	console.log(answer);
	return answer;
};