LeetCode 명상: 가장 긴 증가 하위 시퀀스

이 문제에 대한 설명은 다음과 같습니다.

정수 배열 nums가 주어지면 엄격하게 증가하는 하위 시퀀스 중 가장 긴 길이를 반환합니다.

예:

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.

또는:

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4

또는:

Input: nums = [7, 7, 7, 7, 7, 7, 7]
Output: 1

---

이 시리즈의 이전 문제와 유사하게 여기서도 상향식 동적 프로그래밍 접근 방식을 살펴볼 수 있습니다.

nums 배열의 각 값에 대해 인덱스에서 시작할 수 있는 가장 큰 하위 시퀀스의 길이 $\mathrm{나는}$나는 다음 중 하나입니다:

• 1 (그 가치 그 자체)

또는

• 1 인덱스에서 시작하여 가질 수 있는 가장 큰 부분 시퀀스의 수 $i1$나는 1 .

그러나 nums[i 1]이 nums[i]보다 작은 경우 두 번째 옵션을 포함할 수 없습니다.

먼저 nums의 각 인덱스에서 얻을 수 있는 하위 시퀀스의 길이를 유지하는 dp 배열을 만드는 것부터 시작할 수 있습니다. 즉, dp[0]은 nums[0]부터 가질 수 있는 가장 큰 부분 수열의 길이를 갖고, dp[1]은 nums[1]부터 가질 수 있는 가장 큰 부분 수열의 길이를 가지게 됩니다. 에:

let dp = Array.from({ length: nums.length }, () => 1);

그런 다음 nums의 마지막 인덱스부터 뒤로 반복을 시작할 수 있습니다(이는 값 자체를 취하여 하위 시퀀스를 형성하는 방법이 단 한 가지뿐인 가장 간단한 위치이기 때문입니다).

for (let i = nums.length - 1; i >= 0; i--) {
 /* ... */
}

각 옵션에 대해 다음 인덱스부터 반복하여 해당 인덱스에서 형성될 수 있는 가장 큰 하위 시퀀스를 포함할 수 있는지 확인할 수 있습니다. 그렇다면 dp[i]와 1 dp[ 사이의 최대값을 얻을 수 있습니다. j]:

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

마지막으로 dp에서 가장 큰 값을 반환할 수 있습니다.

function lengthOfLIS(nums: number[]): number {
  /* ... */
  return Math.max(...dp); 
}

최종 솔루션은 다음과 같습니다.

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.

시간과 공간의 복잡성

시간복잡도는 $오(n^2)$O(n2) nums의 각 항목에 대해.
숫자로 된 각 항목을 반복합니다. 공간 복잡도는 $O(n)$O(n) dp 배열을 유지하면 num의 길이가 증가함에 따라 크기도 증가합니다.

---

이것은 이 시리즈의 마지막 동적 프로그래밍 문제였습니다. 다음으로 간격에 관한 새로운 장을 시작하겠습니다. 그때까지 즐거운 코딩하세요.

위 내용은 LeetCode 명상: 가장 긴 증가 하위 시퀀스의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!