[DP] 최대 부분 증가 수열

🚩 최대 부분 증가 수열

 

📖 문제 설명 : N개의 자연수의 수열이 주어질 때, 가장 길게 증가하는 원소의 길이를 찾아라.

ex) 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하는 원소들은  2, 5, 6, 7, 12이다. 따라서 길이는 5이다.

 

💡 i 번째 원소에서 0 ~ i-1 번째 원소를 탐색하면서 자기보다 작은 원소들의 개수를 파악한다.

 

// 최대 부분 증가수열 (DP)

function solution(arr, n) {
  let answer = 0
  let dp = Array.from(Array(n), () => 0)
  dp[0] = 1

  for (let i = 1; i < n; i++) {
    let max = 0
    for (let j = i - 1; j >= 0; j--) {
      if (arr[i] > arr[j]) {
        max = Math.max(max, dp[j])
      }
    }
    dp[i] = max + 1
  }

  //   console.log(dp) 부분 증가 수열 원소
  answer = Math.max(...dp)

  return answer
}

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

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

👨‍💻 코드 설명

1. 삽입 정렬 로직과 유사하다. 위에 힌트에 작성한 것처럼 i 번째 원소에서 0 ~ i-1 번째 원소를 탐색하면서 자기보다 작은 원소들의 개수를 파악한다. 파악한 개수에 +1을 i 번째 원소에 넣어준다.

2. 1번을 수행하고 나면 i 번째는 i-1 번째까지의 수 중에서 자기보다 작은 수들의 개수를 파악할 수 있다.

3. N 번째까지 수행한 후, 배열 원소에서 가장 큰 수를 리턴해준다. 가장 큰 수가 결국 가장 크게 증가하는 수열의 수이기 때문이다.

 

잘못된 설명, 코드, 예외 케이스가 있다면 댓글 남겨주시면 수정하겠습니다.