給你一個整數數組?nums?，找到其中最長嚴格遞增子序列的長度。

子序列?是由數組派生而來的序列，刪除（或不刪除）數組中的元素而不改變其余元素的順序。例如，[3,6,2,7]?是數組?[0,3,1,6,2,2,7]?的子序列。

示例 1：

輸入：nums = [10,9,2,5,3,7,101,18]
輸出：4
解釋：最長遞增子序列是 [2,3,7,101]，因此長度為 4 。

示例 2：

輸入：nums = [0,1,0,3,2,3]
輸出：4

示例 3：

輸入：nums = [7,7,7,7,7,7,7]
輸出：1

關鍵點

• 雙重循環結構：外層循環遍歷每個元素作為子序列結尾，內層循環檢查所有可能的前驅元素

• 遞增條件：只有當?nums[j] < nums[i]?時才考慮狀態轉移

• 時間復雜度：O(n2)，因為有兩層嵌套循環

核心思路

1. 定義狀態：

   • dp[i]?表示以?nums[i]?結尾的最長遞增子序列的長度

   • 初始時每個元素本身就是一個長度為1的子序列，所以初始化?dp?數組全為1

2. 狀態轉移：

   • 對于每個?i（當前元素），檢查所有?j < i（前面的元素）

   • 如果?nums[j] < nums[i]（滿足遞增條件），則嘗試更新?dp[i]：

     dp[i] = Math.max(dp[i], dp[j] + 1)

     這表示如果接在?nums[j]?后面能形成更長的子序列，就更新?dp[i]

3. 記錄結果：

   • 在計算過程中持續維護一個全局最大值?res

   • 最終?res?就是整個數組的最長遞增子序列長度

// Dynamic programming.
class Solution {public int lengthOfLIS(int[] nums) {if(nums.length == 0) return 0;int[] dp = new int[nums.length];int res = 0;Arrays.fill(dp, 1);for(int i = 0; i < nums.length; i++) {for(int j = 0; j < i; j++) {if(nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);}res = Math.max(res, dp[i]);}return res;}
}

示例數組

nums = [10, 9, 2, 5, 3, 7, 101, 18]

算法步驟解析

1. 初始化：

   • 創建dp數組，長度與nums相同，初始值全為1（因為每個元素本身就是一個長度為1的子序列）

   dp = [1, 1, 1, 1, 1, 1, 1, 1]

2. 雙重循環處理：

   • 外層循環：i從0到n-1

   • 內層循環：j從0到i-1

3. 逐步計算過程：

   i=0?(nums[0]=10):

   • j無（因為i=0時j從0到-1）

   • dp保持不變：[1, 1, 1, 1, 1, 1, 1, 1]

   • res=1

   i=1?(nums[1]=9):

   • j=0: nums[0]=10 > nums[1]=9 → 不更新

   • dp保持不變：[1, 1, 1, 1, 1, 1, 1, 1]

   • res=1

   i=2?(nums[2]=2):

   • j=0: nums[0]=10 > nums[2]=2 → 不更新

   • j=1: nums[1]=9 > nums[2]=2 → 不更新

   • dp保持不變：[1, 1, 1, 1, 1, 1, 1, 1]

   • res=1

   i=3?(nums[3]=5):

   • j=0: nums[0]=10 > nums[3]=5 → 不更新

   • j=1: nums[1]=9 > nums[3]=5 → 不更新

   • j=2: nums[2]=2 < nums[3]=5 → dp[3] = max(dp[3], dp[2]+1) = max(1, 2) = 2

   • dp更新為：[1, 1, 1, 2, 1, 1, 1, 1]

   • res=2

   i=4?(nums[4]=3):

   • j=0: nums[0]=10 > nums[4]=3 → 不更新

   • j=1: nums[1]=9 > nums[4]=3 → 不更新

   • j=2: nums[2]=2 < nums[4]=3 → dp[4] = max(dp[4], dp[2]+1) = max(1, 2) = 2

   • j=3: nums[3]=5 > nums[4]=3 → 不更新

   • dp更新為：[1, 1, 1, 2, 2, 1, 1, 1]

   • res=2

   i=5?(nums[5]=7):

   • j=0: nums[0]=10 > nums[5]=7 → 不更新

   • j=1: nums[1]=9 > nums[5]=7 → 不更新

   • j=2: nums[2]=2 < nums[5]=7 → dp[5] = max(dp[5], dp[2]+1) = max(1, 2) = 2

   • j=3: nums[3]=5 < nums[5]=7 → dp[5] = max(dp[5], dp[3]+1) = max(2, 3) = 3

   • j=4: nums[4]=3 < nums[5]=7 → dp[5] = max(dp[5], dp[4]+1) = max(3, 3) = 3

   • dp更新為：[1, 1, 1, 2, 2, 3, 1, 1]

   • res=3

   i=6?(nums[6]=101):

   • j=0: nums[0]=10 < nums[6]=101 → dp[6] = max(dp[6], dp[0]+1) = max(1, 2) = 2

   • j=1: nums[1]=9 < nums[6]=101 → dp[6] = max(dp[6], dp[1]+1) = max(2, 2) = 2

   • j=2: nums[2]=2 < nums[6]=101 → dp[6] = max(dp[6], dp[2]+1) = max(2, 2) = 2

   • j=3: nums[3]=5 < nums[6]=101 → dp[6] = max(dp[6], dp[3]+1) = max(2, 3) = 3

   • j=4: nums[4]=3 < nums[6]=101 → dp[6] = max(dp[6], dp[4]+1) = max(3, 3) = 3

   • j=5: nums[5]=7 < nums[6]=101 → dp[6] = max(dp[6], dp[5]+1) = max(3, 4) = 4

   • dp更新為：[1, 1, 1, 2, 2, 3, 4, 1]

   • res=4

   i=7?(nums[7]=18):

   • j=0: nums[0]=10 < nums[7]=18 → dp[7] = max(dp[7], dp[0]+1) = max(1, 2) = 2

   • j=1: nums[1]=9 < nums[7]=18 → dp[7] = max(dp[7], dp[1]+1) = max(2, 2) = 2

   • j=2: nums[2]=2 < nums[7]=18 → dp[7] = max(dp[7], dp[2]+1) = max(2, 2) = 2

   • j=3: nums[3]=5 < nums[7]=18 → dp[7] = max(dp[7], dp[3]+1) = max(2, 3) = 3

   • j=4: nums[4]=3 < nums[7]=18 → dp[7] = max(dp[7], dp[4]+1) = max(3, 3) = 3

   • j=5: nums[5]=7 < nums[7]=18 → dp[7] = max(dp[7], dp[5]+1) = max(3, 4) = 4

   • j=6: nums[6]=101 > nums[7]=18 → 不更新

   • dp更新為：[1, 1, 1, 2, 2, 3, 4, 4]

   • res=4

最終結果

最長遞增子序列的長度為4。對應的子序列可以是：

• [2, 3, 7, 101]

• 或 [2, 5, 7, 101]

• 或 [2, 3, 7, 18]

• 或 [2, 5, 7, 18]

?