/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 给定数组的最长严格上升子序列的长度。
* @param arr int整型一维数组 给定的数组
* @return int整型
*/
/**
* 解法一:动态规划
* 思路:
* (1)
* 时间复杂度:O(n^2),其中 nn 为数组 nums 的长度。
* 空间复杂度:O(n)O(n),需要额外使用长度为 nn 的 dpdp 数组。
*/
export function LIS(arr: number[]): number {
if (arr.length == 0) return 0
const dp: number[] = []
dp[0] = 1
let maxans = 1
for (let i = 1; i < arr.length; i++) {
dp[i] = 1
for (let j = 0; j < i; j++) {
if (arr[i] > arr[j]) dp[i] = Math.max(dp[i], dp[j] + 1)
}
maxans = Math.max(maxans, dp[i])
}
return maxans
}
/**
* 解法二:贪心 + 二分查找
* 思路:
* (1)
* 时间复杂度:O(nlogn)
* 空间复杂度:O(n)
*/
export function LIS(arr: number[]): number {
if (arr.length == 0) return 0
let len = 1
let n = arr.length
const d: number[] = []
d[len] = arr[0]
for (let i = 1; i < n; ++i) {
if (arr[i] > d[len]) {
d[++len] = arr[i]
} else {
let l = 1
let r = len
let pos = 0
while (l <= r) {
let mid = (l + r) >> 1
if (d[mid] < arr[i]) {
pos = mid
l = mid + 1
} else {
r = mid - 1
}
}
d[pos + 1] = arr[i]
}
}
return len
}
一站式解决前端面试高频算法题