求數(shù)組的最長上升子序列的長度。
動(dòng)態(tài)規(guī)劃
dp[i]為考慮前i個(gè)元素，以第 i 個(gè)數(shù)字結(jié)尾的最長上升子序列的長度，nums[i] 必須被選取。
狀態(tài)轉(zhuǎn)移方程為
dp[i] = max(dp[j]) + 1浓利，其中 0 <= j < i，且nums[j] < nums[i]
- 時(shí)間復(fù)雜度 O(n^2)钞速，計(jì)算狀態(tài)時(shí)dp[i]贷掖，需要O(n)遍歷dp[0]-dp[i-1]
- 空間復(fù)雜度O(n)
- Runtime: 148 ms, faster than 69.52%
- Memory Usage: 39.3 MB, less than 82.00%
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let len = nums.length
if(len === 0) return 0
let dp = Array(len).fill(1)
let max = 1
for (let i = 1; i < len; i++) {
for(let j = 0; j < i; j++) {
if(nums[i] > nums[j]) {
if(dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1
}
}
}
if(max < dp[i]) max = dp[i]
}
return max
};
貪心 + 二分查找
若使上升子序列盡可能地長，需要讓序列上升盡可能慢渴语，因此希望每次在上升子序列最后加上的那個(gè)數(shù)盡可能小苹威。
基于上述的貪心思路，維護(hù)一個(gè)數(shù)組dp[i]驾凶，表示長度為i的最長上升子序列的末尾元素的最小值牙甫，len記錄目前最長上升子序列的長度掷酗，起始時(shí) len 為 1，d[1] = nums[0]
dp[i] 基于i 是單調(diào)遞增的窟哺。證明：前提 j < i泻轰，dp[j] >= dp[i]，考慮長度為 i 的最長上升子序列的末尾刪除 i-j個(gè)元素且轨，j的末尾元素小于d[i]且小于d[j]浮声，找到長度為j的最長上升子序列，末尾元素小于 d[j]旋奢，得證泳挥。
依次遍歷 nums 中的每個(gè)元素，更新數(shù)組 dp 和 len 的值黄绩，如果 nums[i] > nums[len]羡洁，則更新 len = len + 1玷过，否則在 dp[1,...len] 中尋找 dp[i - 1] < nums[j] < dp[i]爽丹，可以根據(jù)數(shù)組的的單調(diào)性，使用二分查找尋找下標(biāo) i
- 時(shí)間復(fù)雜度O(nlogn)
- 空間復(fù)雜度O(n)
- Runtime: 80 ms, faster than 98.01% o
- Memory Usage: 39.1 MB, less than 93.13%
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function(nums) {
let len = nums.length
if(len === 0) return 0
let d = []
d[1] = nums[0]
let flag = 1
for(let i = 1; i < len; i++) {
if(d[flag] < nums[i]) {
d.push(nums[i])
flag++
} else {
let start = 1
let end = flag
let pos = 0
while(start <= end) {
let mid = (start + end) >> 1
if(d[mid] < nums[i]) {
start = mid + 1
pos = mid
} else {
end = mid -1
}
}
d[pos + 1] = nums[i]
}
}
return flag
};
