引言

這兩道題有很大的相似性，在這里主要的地方就是循環的設置，不僅僅適用于這兩道題，在很多類似的題目中都可以用到，要學會相應的方法才行；

最長遞增子序列

給你一個整數數組 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

提示：
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

這道題要求最長遞增子序列，并沒有要求連續，題解：
1，dp[i]表示0~i 的最長遞增子序列長度
2，位置 i 的最長遞增子序列為 j 從0到 i-1 各個位置的最長升序子序列加 1 的最大值
則有 if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

這里不是要dp[i]與dp[j] + 1進行比較，目的是要取dp[j] + 1的最大值
因為隨著dp[i]逐漸增大，最后一定取到的是dp[j]最大值

3，對于每一個 i ，對應的dp[i]初始大小最小為1.
4，由轉移方程可以知道循環是從前到后的，j 是0~i - 1內的范圍，所以 j 循環是內循環；

代碼如下：

class Solution { public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n <= 1) return n;vector<int> dp(n, 1);int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < i; ++j) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}ans = max(ans, dp[i]);}return ans;} };

這道題因為不是連續的，所以在循環時需要把 i 之前的所有情況都來一遍，由此找到最長遞增子序列；可以理解為 j 始終就是 i 之前的位置。

最長連續遞增序列

給定一個未經排序的整數數組，找到最長且連續遞增的子序列，并返回該序列的長度。
連續遞增的子序列 可以由兩個下標 l 和 r（l < r）確定，如果對于每個 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是連續遞增子序列。

示例 1：
輸入：nums = [1,3,5,4,7]
輸出：3
解釋：最長連續遞增序列是 [1,3,5], 長度為3。
盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續的，因為 5 和 7 在原數組里被 4 隔開。

示例 2：
輸入：nums = [2,2,2,2,2]
輸出：1
解釋：最長連續遞增序列是 [2], 長度為1。

提示：
0 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

這個題和上一題唯一不同就是求的是連續的子序列，所以步驟會少一些，因為如果求第 i 個位置的只需要考慮前一個 i - 1 位置就可以了，不像上一道需要考慮 i 之前的所有情況；

1，dp[i]表示0~i 的最長連續遞增子序列長度；
2，由于只需要考慮前一個，所以只要 nums[i] > nums[i - 1]，那么以 i為結尾的數組的連續遞增的子序列長度 一定等于以 i - 1 為結尾的數組的連續遞增的子序列長度 + 1
則有 if (nums[i - 1] < nums[i]) dp[i] = dp[i - 1] + 1;
3，以下標 i 為結尾的數組的連續遞增的子序列長度最少也應該是1，即就是nums[i]這一個元素，所以dp[i]應該初始化為1
4，因為dp[i]是由dp[i - 1] 得來的，所以遍歷順序是從前往后；

代碼如下:

class Solution { public:int findLengthOfLCIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1);int ans = 1;for (int i = 1; i < n; ++i) {if (nums[i - 1] < nums[i])dp[i] = dp[i - 1] + 1;ans = max(ans, dp[i]);}return ans;} };

總結

這兩道題主要注意的地方就是不連續和連續的區別，有很多題目會有這兩種情況，所以如果題目讓求
不連續的，你就需要考慮 i 之前的所有情況，這就需要多寫一個 j 作為內循環遍歷所有情況
連續的，只需要考慮前一個與 i 的關系就可以了；

總結

以上是生活随笔為你收集整理的最长递增子序列 最长连续递增序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。