최장 증가 수열의 길이(LIS) 다음과 같은 수열이 있을 때 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분의 수열의 길이를 말함. -> 3,2,6,4,5,1 일 경우는 2,4,5 | 3,5,6 => 즉, 3 이다. 이걸 구하는 알고리즘이 LIS이다. Brute-force 방법으로 푼다면 길이가 0 일때 모든 부분집합. 1일 때 2일 때 ... 쭉 불가능 할 때 까지 가는 것이다. 이 경우 같은 경우 부분집합의 총 개수가 2^N이기 때문에 O(2^n)이 나오게 된다. Dynamic programming(DP) 숫자열 - a,b,c,d,e .... LIS[i] : a,b,c,d,e에서 가장 긴 부분 수열의 길이라 하면 1번 : LIS(i)가 i번째 원소를 포함하지 않는다면, LIS(i) = LIS..