[LIS]최대 부분 증가 수열

문제

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

 

문제풀이

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 일컫음

---

해당 문제에서 길이가 최대인 부분수열의 값만을 참조하여 1을 가산한다는 풀이는 다음 포스팅의 문제를 풀어 봄으로써 좀 더 쉽게 이해할 수 있었다.

https://choi95.tistory.com/33?category=854389 

보이는 학생

 

코드

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; //어떠한 원소의 값보다 크지 않을 경우 그 값이 자기 자신만을 포함한 경우의 수인 1로 초기화 될 수 있도록
    for(let j = i - 1; j >= 0; j--) {
      if(arr[i] > arr[j] && dy[j] > max) { //이전 원소보다 크고 해당 원소의 부분수열이 최장일 경우
        max = dy[j];
      }
    }
    dy[i] = max + 1;
  }
  answer = Math.max(...dy);
  return answer;
}

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

---

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;
                    for(let j=i-1; j>=0; j--){
                        if(arr[j]<arr[i] && dy[j]>max){
                            max=dy[j];
                        }
                    }
                    dy[i]=max+1;
                    answer=Math.max(answer, dy[i]);
                }
                return answer;
            }

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