题目链接 难度：中等
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
思路历程
- 首先明确问题，带着问题找解决办法
- 题目给定了一个数组
nums，需要找出其中最长严格递增子序列的程度
- 严格递增子序列：需要保证子序列数组元素不重复
- ex：
nums = [10, 9, 2, 5, 3, 7, 101, 18]输出：4
- 最长递增子序列是：
[2, 3, 7, 101]所以输出：4
学习题解
动态规划
- 可以定义 代表前个元素
- 其意义是，以第
个数字结尾的最长子序列的长度
- 然后可以从小到大计算
数组的值，在计算
之前，肯定已经计算出了
的值
- 则状态转移方程为
- 以数组
nums = [10, 9, 2, 5, 3, 7, 101, 18]为例，过程如下
- 对于元素
10而言，子序列为1——dp[0] = 1 - 元素
9——子序列为9——dp[1] = 1 - 元素
2——子序列为2——dp[2] = 1 - 元素
3——子序列为2,3——dp[3] = 2 - 以此类推
code+理解
public int lengthOfLIS(int[] nums) {
// 动态规划解决，首先需要获取数组的长度.
int n = nums.length;
// 创建 dp 数组
int[] dp = new int[n];
// 定义变量输出最终结果值
int ans = 0;
// 循环数组处理数据
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]);
}
}
dp[i] += 1;
ans = Math.max(dp[i], ans);
}
return ans;
}- 根据状态转移方程，可以知道我们需要做的事情是
- 寻找索引和值都小于当前元素的 值.
- 目标值能够与当前元素所构成的 最长递增子序列 长度+1
- 然后在 循环过程中找到 最长递增的子序列
动态规划+二分查找
- “贪心”——如果想要使上升子序列尽可能的长，那么在构建子序列的时候，期望最后加入的数字尽可能地小。
- 以数组
nums = [10, 9, 2, 5, 3, 7, 101, 18]为例 - 维护一个数组
int[] lis = new int[n];来存放 最长递增子序列
- 遍历到元素
10——最长递增子序列为[10]长度为1 - 遍历到元素
9——最长递增子序列为[9]长度为1
- 为什么更新最长递增子序列为
[9]? - 因为 9 比 10 小，在向后遍历过程中的话，很显然以元素
9开头更有可能构成一个最长的递增子序列
- 遍历到元素
2——最长递增子序列为[2]长度为1 - 遍历到元素
5——最长递增子序列为[2, 5]长度为2 - 遍历到元素
3——最长递增子序列为[2, 3]长度为2 - 遍历到元素
7——最长递增子序列为[2, 3, 7]长度为3 - 遍历到元素
101——最长递增子序列为[2, 3, 7, 101]长度为4 - 遍历到元素
18——最长递增子序列为[2, 3, 7, 18]长度为4
- 那么算法就变成了，每遍历一个新的元素，需要判断其是否能够加入到
lis数组中去
- 比数组
lis末尾元素大，那么追加 - 比数组
lis末尾元素小，那么替换
code+理解
public int best(int[] arr) {
int n = arr.length;
// 定义一个数组，用来存放最长递增 子序列.
int[] lis = new int[n];
int pos = 0;
for (int num : arr) {
// 这个时候要去寻找 pos 在数组中的位置.
int left = 0, right = pos;
// 二分查找：这里查找什么？
// 查找元素 num 是否能在 lis 数组中找到最接近且大于的元素.
// 由于初始化 right = pos = 0，直接跳过二分查找步骤
// 进入二分查找的逻辑的话，就要去寻找 最接近 num 的元素
// ---即，寻找第一个比当前 num 元素大的元素.
// 如果能找到的话--进行替换
// 如果找不到的话--进行追加
while(left < right) {
int mid = left + (right - left) / 2;
if(lis[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
lis[left] = num;
if(left == pos) {
pos++;
}
}
return pos;
}