🎒 공부/알고리즘

LIS

LIS LIS; Longest Increasing Subsequence 최장 증가 부분 수열 original array의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열 LIS 길이 구하기 1. DP - O(N^2) length를 아래와 같이 정의할 때, DP를 활용하여 LIS의 길이를 구할 수 있다. length[i]: i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이 이때 length.size == array.size 이다. for (i in array.indices) { length[i] = 1 for (j in 0 until i) { if (array[j] < array[i]) length[i] = max(length[i..