【每日一题】【二分mid&贪心】2022年2月8日-NC163 最长上升子序列(一)
1、描述
给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
2、介绍
最长递增子序列（longest increasing subsequence），简称LIS
3、方法1：贪心+二分
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定数组的最长严格上升子序列的长度。
* @param arr int整型一维数组 给定的数组
* @return int整型
*/
public int LIS (int[] arr) {
int len = 1, n = arr.length;
if(n == 0) {
return 0;
}
int[] lisArr = new int[n + 1];
lisArr[len] = arr[0];
for(int i = 1; i < n; i++) {
//len代表lisArr中的最后一个元素
if(lisArr[len] < arr[i]) {
lisArr[++len] = arr[i];
} else {
//二分，在lisArr数组中找比arr[i]小的，最靠后的位置pos
//未找到，即lisArr数组中所有元素均大于arr[i]
//需要更新lisArr数组的位置，为何不设为1呢？
int l = 1,r = len, pos = 0;
while(l <= r) {
//int mid = l + (r - l) >> 1;是错误的，原因是优先级导致的
int mid = l + ((r - l) >> 1);//位运算是为了避免溢出
//int mid = (l + r) >> 1;
if(lisArr[mid] < arr[i]) {
//更新指针
l = mid + 1;
pos = mid;
} else {
r = mid - 1;
}
}
//循环结束，找到了pos
lisArr[pos + 1] = arr[i];
//pos是最后一个位置，len不变
//pos是中间位置，len仍不变，元素继续往后填
//所以没有必要更新len位置
}
}
return len;
}
}
4、二分使用库函数实现
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定数组的最长严格上升子序列的长度。
* @param arr int整型一维数组 给定的数组
* @return int整型
*/
public int LIS (int[] arr) {
//使用二分查找确定插入位置
//贪心
int n = arr.length, len = 1;
if(n <= 1) {
return n;
}
int[] lisArr = new int[n + 1];
lisArr[len] = arr[0];
for(int i = 1; i < n; i++) {
if(lisArr[len] < arr[i]) {
lisArr[++len] = arr[i];
} else {
//从1开始
int res = Arrays.binarySearch(lisArr, 1, len + 1, arr[i]);
if(res >= 0) { //表示找到了插入位置
//即存在相同元素时，跳过
continue;
} else { //表示没有找到插入位置
//则res<0
//其值表示应插入位置的负数
int ins = -(res + 1);
lisArr[ins] = arr[i];
}
}
}
return len;
}
}
5、方法2：动态规划
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定数组的最长严格上升子序列的长度。
* @param arr int整型一维数组 给定的数组
* @return int整型
*/
public int LIS (int[] arr) {
//动态规划实现
//最长子序列应当使用max值记录
int n = arr.length;
if(n == 0) {
return 0;
}
int[] dp = new int[n];
Arrays.fill(dp, 1);
int maxLen = Integer.MIN_VALUE;
for(int i = 0; i < n; i++) {
for(int j = 0; j < i; j++) {
if(arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}
}