Zayden

leetcode - Longest Increasing Subsequence

July 30, 2023

문제 설명

정수 배열의 숫자가 주어지면, 엄격하게 증가하는 가장 긴 길이의 서브 시퀀스.

  • 예시 1
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
  • 예시 2
Input: nums = [0,1,0,3,2,3]
Output: 4
  • 예시 3
Input: nums = [7,7,7,7,7,7,7]
Output: 1

제약 조건:

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

문제 접근

동적 계획법을 이용하여 접근합니다. 배열의 두번째 자료부터 시작하여 이전 요소와 비교합니다.

  1. nums 배열의 길이만큰 빈 배열을 생성아여 모든 요소를 1로 채웁니다.
  2. 기준을 두번째 자료부터 시작하여 이전 요소까지 비교합니다.
  3. 기준 자료가 비교 대상보다 크면 1로 채운 배열을 업데이트 합니다.
  4. 해당 반복문을 마치고 temp 배열에 가장 큰 요소를 반환합니다.
function soultion(nums) {
  const temp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        temp[i] = Math.max(temp[i], temp[j] + 1);
      }
    }
  }

  return Math.max(...temp);
};