문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

처음엔 그냥 max값을 0으로 시작해서 이것보다 큰 수의 갯수를 세면 될꺼라 생각하고 풀었는데 틀린 답이었다...[100, 30, 10, 20, 50, 40]과 같이 처음 값이 큰수가 되면 처음 값보다 더 큰값만 구하게 되고, 이후 작은 작은 수로 시작하는 더 긴 수열이 나올 수도 있다...

문제를 푸는 방법은 마지막 수의 이전 값을 비교하면 된다.
수열의 갯수만큼 1로 채워진 배열 dp를 만들고,(자기 자신부터 시작하므로)
각 값은 n번까지 왔을때 가장 긴 수열의 갯수이다.

numbers = [100, 30, 10, 20, 50, 40] 이라는 배열이 있을때
dp[0]
1(자기 자신밖에 없으므로)

dp[1]
numbers[0]과 number[1]을 비교하여 만약 numbers[0]이 작을 경우 dp[1] = dp[0] + 1이 된다.

dp[2]
numbser [0], numbers[1]을 각각 number[2]와 비교하여 numbers[2]보다 작을 경우 dp[0], dp[1]중 더 큰 값을 dp[2]와 더한다.(그게 dp[2]이전에 있던 가장 긴 수열의 갯수이므로)
...

코드

var fs = require('fs');
let [N, ...array] = fs
	.readFileSync('./input.txt')
	.toString()
	.trim()
	.split('\n');

const numbers = array[0].split(' ');

function solution() {
	const dp = Array(+N).fill(1);

	for (let i = 1; i < numbers.length; i++) {
		let max = 0; //만약 작은 수가 없다면 dp[i]에 0을 더하게 된다.

		for (let j = 0; j < i; j++) {
			if (+numbers[j] < +numbers[i]) {
              //현재 비교하는 값보다 작은 수가 있는 경우 그 값까지의 최대 수열수를 max와 비교해 더 큰값이 max가 된다.
				max = Math.max(max, dp[j]);
			}
		}
		dp[i] = dp[i] + max;
	}
	console.log(Math.max(...dp));
}

solution();