최장 증가 부분순열은 순열의 부분순열 집합에서 오름차순으로 정렬된 부분순열 중에 길이가 가장 긴 부분순열을 구하는 알고리즘
먼저 최장 증가 부분순열의 길이를 계산하기 위해 길이 배열을 계산한다. 그 후에 길이 배열을 활용하여 역추적을 하면 최장 증가 부분순열을 구할 수 있다. 역추적 과정은 DFS를 활용했다.
const LIS = (set) => {
const getIndexArray = (array, maxLength) => {
return array
.map((length, index) => {
return { length, index };
})
.filter(({ length, index }) => length === maxLength)
.map(({ length, index }) => index);
};
const length = set.length;
const lengthArray = Array(length).fill(1);
for (let i = 1; i < length; i++) {
for (let j = 0; j < i; j++) {
if (set[i] >= set[j]) {
lengthArray[i] = Math.max(lengthArray[i], lengthArray[j] + 1);
}
}
}
const maxLength = Math.max(...lengthArray);
const maxIndexes = getIndexArray(lengthArray, maxLength);
const answer = [];
while (maxIndexes.length > 0) {
const maxIndex = maxIndexes.pop();
const stack = [[maxLength, maxIndex, [set[maxIndex]]]];
while (stack.length > 0) {
const [length, currentIndex, sequence] = stack.pop();
if (length === 1) {
answer.push(sequence);
continue;
}
const indexArray = getIndexArray(lengthArray, length - 1);
indexArray.forEach((index) => {
if (index < currentIndex && set[index] < sequence[0]) {
const copiedSequence = sequence.slice();
copiedSequence.unshift(set[index]);
stack.push([length - 1, index, copiedSequence]);
}
});
}
}
return answer;
};