가장 긴 증가하는 부분 수열 (LIS problem)

Longest Increasing Subsequence

길이가 1이상인 수열이 주어질 때,

가장 길고, 증가하는 부분 수열의 길이를 찾는 문제

 

다이나믹 프로그래밍(DP, Dynamic Programming)을 사용해야 한다.

 

1. 시간 복잡도가 N^2인 알고리즘

A = { 10, 20, 30, 10, 20, 50 }

 

DP에 넣어야 하는 정보는 A[ i ]로 끝나는 가장 긴 증가하는 부분 수열의 길이이다.

 

1 ) 인덱스 1은 무조건 1의 길이를 갖는다.

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1

 

2 ) 두 번째 부터는 A[ 0 ]부터 A[ i - 1 ]중에 A[ i ]보다 작은 값을 찾고,

      해당 인덱스의 DP가 가장 큰 값을 찾는다.

      그리고 해당 DP의 값에 1을 더한 값이 DP[ i ]이다.

 

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1	2

     step 1. A[ 0 ]부터 A[ i - 1]중에 A[ i ]보다 작은 수의 인덱스

                    0, 1

     step 2. 위의 인덱스 중, DP가 가장 큰 값의 인덱스

                    1

 

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1	2	3

     step 1. A[ 0 ]부터 A[ i - 1]중에 A[ i ]보다 작은 수의 인덱스

                    0, 1, 2

     step 2. 위의 인덱스 중, DP가 가장 큰 값의 인덱스

                    2

 

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1	2	3	1

     step 1. A[ 0 ]부터 A[ i - 1]중에 A[ i ]보다 작은 수의 인덱스

                    0

     step 2. 위의 인덱스 중, DP가 가장 큰 값의 인덱스

                    0

 

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1	2	3	1	2

     step 1. A[ 0 ]부터 A[ i - 1]중에 A[ i ]보다 작은 수의 인덱스

                    0, 1, 4

     step 2. 위의 인덱스 중, DP가 가장 큰 값의 인덱스

                    1, 4

 

index	0	1	2	3	4	5	6
A	0	10	20	30	10	20	50
DP	0	1	2	3	1	2	4

     step 1. A[ 0 ]부터 A[ i - 1]중에 A[ i ]보다 작은 수의 인덱스

                    0, 1, 2, 3, 4, 5

     step 2. 위의 인덱스 중, DP가 가장 큰 값의 인덱스

                    3

 

 

자바스크립트 코드

let dp = [0, 1];
for (let i = 2; i <= n; i++) {
  let max = 0;

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

  dp.push(max + 1);
}

console.log(Math.max(...dp));