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 配列の各値について、インデックス から始まる最大のサブシーケンスの長さ $私$私 次のいずれかです:

• 1 (その値自体)

または

• 1 インデックスから始まる最大のサブシーケンスの番号 $i1$私1 。

ただし、nums[i 1] が nums[i] より小さい場合、2 番目のオプションを含めることはできません。

まず、nums 以降の各インデックスから保持できるサブシーケンスの長さを保持する dp 配列を作成することから始めます。つまり、dp[0] は nums[0] 以降の最大のサブシーケンスの長さを持ち、dp[1] は nums[1] 以降の最大のサブシーケンスの長さを持ちます。に:

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

次に、nums の最後のインデックスから逆方向に反復処理を開始できます (値自体を取得するだけで、後続のサブシーケンスを形成する方法が 1 つだけある最も単純な位置であるため)。

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.

時間と空間の複雑さ

時間計算量は次のとおりです。 $O(n^2)$O(n2) nums の各項目 nums の各項目を反復処理します。
空間の複雑さは、 $O(n)$O(n) dp 配列を保持しており、nums の長さが増加するにつれてそのサイズも増加します。

---

これは、このシリーズの最後の動的計画問題でした。次に、インターバルに関する新しい章を開始します。それまで、コーディングを楽しんでください。

以上がLeetCode 瞑想: 最長の増加サブシーケンスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。