C国演义 [第六章]

第六章

• 最长递增子序列
• • 题目理解
  • 步骤
  • • dp含义
    • 递推公式
    • 初始化
    • 遍历顺序
    • 代码
    • 最长连续递增序列
    • • 题目理解
      • 步骤
      • • dp含义
        • 递推公式
        • 初始化
        • 遍历顺序
        • 代码

          最长递增子序列

          力扣链接

          给你一个整数数组 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 3, dp[4] = max(dp[4], dp[1] + 1) = max(2, 3) = 3

            j 遍历到 7, 9 > 7, dp[4] = max(dp[4], dp[2] + 1) = max(3, 4) = 4

            j 遍历到 5, 9 > 5, dp[4] = max(dp[4], dp[3] + 1) = max(4, 4) = 4

            初始化

            🗨️由递推公式得知: 都是从dp[0] 推导上去的, dp[0] 该怎样初始化呢?

            • 回顾一下dp的含义 — — 以nums[i]结尾的最长递增子序列的长度

              那么dp[0] — — 以nums[0]结尾的最长递增子序列的长度 — — 那么dp[0] = 1

              🗨️那么其他的应该怎样初始化?

              • 每一个数, 都是一个递增子序列 — — 其他的也应该初始化为 1

                ⇒dp数组都初始化为1

                遍历顺序

                由递推公式得知: 是由前到后的顺序

                那么遍历顺序就是, 从小到大

                代码

                class Solution {
                public:
                    int lengthOfLIS(vector& nums) 
                    {
                        // 初始化
                        // dp[i] -- -- 以dp[i]结尾的最长递增子序列的最大长度
                        vector dp(nums.size(), 1);
                        
                        int result = 1;  // 记录最长递增子序列的最大长度
                                        // 初始化为 1 -- -- 也是为了避免讨论一个数的情况
                        for(int i = 1; i  nums[j])
                                    dp[i] = max(dp[j] + 1, dp[i]);
                            }
                            
                            result = max(result, dp[i]);
                        }
                        
                        return result;
                    }
                };
                

                最终的结果并不是 dp[nums.size() - 1],

                而是需要遍历dp[i], 然后找到一个最大值

                举个例子:

                nums = [1, 3, 5, 7, 6 ], 我们发现: 最长递增子序列是 1, 3, 5, 7

                是以 7结尾的, 而不是以 6结尾的

                

                最长连续递增序列

                力扣链接

                给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

                连续递增的子序列 可以由两个下标 l 和 r（l