動态規劃總結最長子序列

​

最長連續遞增序列

題目

給定一個未經排序的整數數組，找到最長且 連續遞增的子序列，并傳回該序列的長度。

連續遞增的子序列 可以由兩個下标 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

解題思路

根據題意，本題可用動态規劃的方式來求解。

第一步，确定dp數組以及下标的含義：

dp[i]：以下标i為結尾的數組的連續遞增的子序列長度為dp[i]。

第二步，确定遞推公式：

如果 nums[i + 1] > nums[i]，那麼以 i+1 為結尾的數組的連續遞增的子序列長度一定等于 以 i 為結尾的數組的連續遞增的子序列長度 + 1 。是以可以得出遞推公式為：dp[i + 1] = dp[i] + 1;

第三步，dp 數組初始化：

連續遞增的子序列長度最少是 1， 是以 dp 數組應該初始化為 1。

第四步，确定周遊順序：

從遞推公式上可以看出， dp[i + 1]依賴dp[i]，是以一定是從前向後周遊。

代碼實作

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length == 0){
            return 0;
        };
        int count = 1;
        int len = nums.length;
        int[] dp = new int[len];
        for(int i = 0; i < len; i++){
            dp[i] = 1;
        }

        for(int i = 0; i < len - 1; i++){
            if(nums[i+1] > nums[i]){
                dp[i+1] = dp[i] + 1;
            }
            if(dp[i+1] > count) count = dp[i+1];
        }

        return      

時間複雜度

• 時間複雜度：O(n)，其中 n 是數組 nums 的長度。
• 空間複雜度：O(1)。

最長遞增子序列

題目

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

解題思路

根據題意，此題可以用動态規劃的方式來求解。

第一步，确定 dp 數組以及下标的含義：

dp[i] 表示 i 之前包括 i 的以 nums[i] 結尾最長上升子序列的長度。

第二步，确定遞推公式：

位置i的最長升序子序列等于 j 從 0 到 i-1 各個位置的最長升序子序列 + 1 的最大值。遞推公式為：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

第三步，初始化：

dp[i] 的起始大小是 1。

第四步，确定周遊順序：

dp[i] 是有0到i-1各個位置的最長升序子序列推導而來，那麼周遊i一定是從前向後周遊。j其實就是0到i-1，周遊i的循環在外層，周遊j則在内層。

代碼實作

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      

時間複雜度

• 時間複雜度：O(n^2)，其中 n 為數組 nums 的長度.
• 空間複雜度：O(n).

1. 閱讀完記得給我點個贊哦，有👍 有動力
2. 關注公衆号---HelloWorld傑少，第一時間推送新姿勢