N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다.
첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고, 둘째 줄은 N개의 입력데이터들이 주어진다.
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
8
5 3 7 8 6 2 9 4
4
원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열
arr를 2중 for문으로 순회 하는데, 가장 첫 번째 값의 경우 비교 할 대상이 없으므로 dy에 초기화 한다.
그 다음 arr 요소 부터 arr의 i번째와 arr의 j번째와 비교하고, i가 더 크고, 만약 max값보다 dy[j]가 더 크다면 dy[j]를 max 값에 추가 시킨다. 하지만, 현재는 5보다 3이 더 작고, 더 이상 비교 대상이 없으므로 1이 된다.
7의 경우 {3,7}, {5,7}
2가지 경우의 수가 존재하므로, max 값 + 1이 되어 2가 된다.
9의 경우 {3,7,8,9}, {5,7,8,9}
총 4가지 경우의 수가 존재하므로 기존 max 값인 3의 1을 더한 4가 된다.
모두 순회 후 dy에서 가장 큰 값인 4가 정답이 된다.
function solution(arr) {
let size = arr.length;
// dynamic array 생성
let dy = Array.from({ length: size }, () => 0);
let answer = 0;
// dy 첫번째 요소 1로 초기화
dy[0] = 1;
// 전체 요소 순회
for (let i = 1; i < size; i++) {
// max 초기화
let max = 0;
for (let j = 0; j <= i; j++) {
// 만약 오름 차순 수열이 가능하고, dy[j]이 max보다 크다면
if (arr[i] > arr[j] && dy[j] > max) {
// max에 dy[j] 할당
max = dy[j];
}
}
// dy[j]가 돌면서 arr[i]가 포함되지 않은 최대 오름 차순 수열의 길이 = max
// 즉, 기존 max값에 자신이 포함된 길이가 새로운 max값이 된다.
dy[i] = max + 1;
// 기존 answer값과 dy[i] 비교 하며 큰 값을 answer에 할당
answer = Math.max(answer, dy[i]);
}
return answer;
}
console.log(solution([5, 3, 7, 8, 6, 2, 9, 4]));