Algorithm LIS

문제

정수를 요소로 갖는 문자열을 입력받아 다음의 조건을 만족하는 LIS의 길이를 리턴

• LIS : 배열의 연속되지 않는 부분 배열 중 모든 요소가 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열
• 배열 [1, 2, 3]의 subseqeunce는 [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]
• 엄격한 오름차순 : 배열이 동일한 값을 가진 요소없이 오름차순으로 정렬되어 있는 경우

인자

• number 타입을 요소로 갖는 배열
• arr.length는 60,000 이하
• arr[i]는 100,000 이하 정수

주의사항

• LIS의 길이를 리턴
• LIS가 존재하지 않는 경우는 없다.

const LIS = function (arr) {
  const N = arr.length;
  // lis[i]는 i에서 끝나는 LIS의 길이를 저장
  // 최소한 각 요소 하나로 LIS를 만들 수 있으므로 1로 초기화한다.
  const lis = Array(N).fill(1);
  for (let i = 1; i < N; i++) {
    // i에서 끝나는 LIS의 길이
    for (let j = 0; j < i; j++) {
      // i 이전의 인덱스만 검사하면 된다.
      // i는 1부터 시작하므로, 짧은 길이부터 검사한다. (bottom-up 방식)
      if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
        lis[i] = lis[j] + 1;
      }
    }
  }
  return Math.max(...lis);
};