前置知识: 讲解006 - 二分搜索 讲解066 - 一维动态规划 【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

本节课讲述：最长递增子序列 & 最长不下降子序列 的最优解，以及一些扩展题目

注意： 本节课讲述的是最优解，时间复杂度是O(n*logn)，空间复杂度O(n)，好实现、理解难度不大 这个问题也可以用线段树来求解，时间和空间复杂度和本节讲的最优解没有区别，但需要理解线段树 线段树会在【扩展】课程阶段讲述

题目1 最长递增子序列 给定一个整数数组nums 找到其中最长严格递增子序列长度、最长不下降子序列长度 测试链接 : https://leetcode.cn/problems/longest-increasing-subsequence/

最长不下降子序列 只需要改写二分策略即可

题目2 俄罗斯套娃信封问题 给你一个二维整数数组envelopes 其中envelopes[i]=[wi, hi] 表示第 i 个信封的宽度和高度 当另一个信封的宽度和高度都比这个信封大的时候 这个信封就可以放进另一个信封里，如同俄罗斯套娃一样 请计算 最多能有多少个信封能组成一组“俄罗斯套娃”信封 即可以把一个信封放到另一个信封里面，注意不允许旋转信封 测试链接 : https://leetcode.cn/problems/russian-doll-envelopes/

题目3 使数组K递增的最少操作次数 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k 如果对于每个满足 k <= i <= n-1 的下标 i 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数 请你返回对于给定的 k ，使数组变成K递增的最少操作次数 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/

题目4 最长数对链 给你一个由n个数对组成的数对数组pairs 其中 pairs[i] = [lefti, righti] 且 lefti < righti 现在，我们定义一种 跟随 关系，当且仅当 b < c 时 数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面 我们用这种形式来构造 数对链 找出并返回能够形成的最长数对链的长度 测试链接 : https://leetcode.cn/problems/maximum-length-of-pair-chain/

题目5 有一次修改机会的最长不下降子序列 给定一个长度为n的数组arr，和一个整数k 只有一次机会可以将其中连续的k个数全修改成任意一个值 这次机会你可以用也可以不用，请返回最长不下降子序列长度 1 <= k, n <= 10^5 1 <= arr[i] <= 10^6 测试链接 : https://www.luogu.com.cn/problem/P8776

预告 最长递增子序列的数量问题 给定一个未排序的整数数组nums，返回最长递增子序列的个数 测试链接 : https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

这个问题的最优解能做到O(n * logn) 会放在【扩展】课程阶段，详解树状数组(index tree)的时候来讲解 用这个高级数据结构来求解这个题会很方便

这里为什么要提呢？主要是想说：巧妙构思 vs 成熟体系

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com