최대 부분 증가수열

문제

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

제한사항

• 첫째 줄은 입력되는 데이터의 수 N(1≤N≤1,000, 자연수)를 의미하고,
• 둘째 줄은 N개의 입력데이터들이 주어진다.

입출력 예

풀이

• 최대(최장) 부분 증가수열 : 수열의 부분 수열 중 오름차순으로 되어있는 것을 증가 부분 수열이라고 하고 이러한 수열 중 가장 긴 수열을 최장 부분 증가수열이라 한다.

function solution(arr) {
  let answer = 0;
  let dy = Array.from({ length: arr.length }, () => 0);
  dy[0] = 1;
  for (let i = 1; i < arr.length; i++) {
    let max = 0;
    // 현재 원소기준 뒤를 살피면서 가장 큰 dy값을 max로하고
    // 다만 그 원소가 현재 원소보단 작아야한다.
    // 증가 수열의 조건을 지키기 위해.
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] < arr[i] && dy[j] > max) {
        max = dy[j];
      }
    }
    // 더하기 1해준다.
    dy[i] = max + 1;
    answer = Math.max(answer, dy[i]);
  }
  console.log(dy);
  return answer;
}

let arr = [5, 3, 7, 8, 6, 2, 9, 4];
console.log(solution(arr));

• dy[i]의 의미가 중요한데, arr[i]가 마지막 요소인 증가수열의 개수를 의미한다.
• dy[0]은 arr[0] 즉, 5가 마지막인 증가수열의 개수이다. 5한개 임으로 1로 할당하고 시작하는 것이다.
• dy[1]은 arr[1] 즉, 3이 마지막은 증가수열의 개수인데, 이경우도 1개이다 왜냐면 arr[1]의 앞 요소중에 더 작은 값이 없음으로 자기자신만 가능한 것이다.
• 만약 작은 값이 있다면 개수중 가장 큰 값에 +1 값을 현 dy[i]에 넣으면 된다.
• max값을 계속 0으로 설정하는 이유는 앞에 작은 값이 하나도 없어 max가 그대로 0으로 나오면 거기에 +1을 하여 자기자신의 경우를 생각해주기 위함이다.