“This is the 14th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”
First, an appetizer. Given an unsorted array of integers, find the longest continuously increasing subsequence and return the length of that sequence.
Nums = [1,3,5,4,7] // the longest continuous increasing sequence is [1,3,5] with length 3.Copy the code
-
We first analyze continuous increment I > 0 && nums[i-1] <= nums[I] // start position greater than 0 is currently larger than the previous bit or equal to constitute continuous increment
-
Then record the length at this time i-start+1, we want to save the temporary length ans, and compare it to the previous length to take the maximum math.max (ans, i-start+1), at the end of the loop will be our maximum length.
// Complete the code
let start = 0
let ans = 0
for(let i = 0; i< nums.length; i++){
if(i>0 && nums[i]<= nums[i-1]){
start = i
}
ans = Math.max(ans, i-start +1)}return ans
Copy the code
Now let’s go to the analysis of leetcode300. Given an integer array nums, find the length of the longest strictly increasing subsequence.
-
The longest strict increment can only be greater than the preceding one, equal does not count
-
We use dynamic programming
- So let’s initialize one
dp
Each element of the array is1
. - The outer loop uses a temporary variable
max
, takeMath.max(dp[i], max)
- And then compare it from index I -1
Max (dp[I],dp[j] + 1)
// Complete the code
// Determine the boundary
const n = nums.length
if(n <= 1) {return n
}
let max = 0
const dp = new Array(n).fill(1) / / initialization
for(let i = 1; i < n; i++){
for(let j = i-1; j>=0; j--){
// Strictly incrementing
if(nums[i] > nums[j]){
Dp [j] +1 = nums[I] +1 = nums[I
dp[i] = Math.max(dp[i], dp[j] + 1)
}
}
max = Math.max(d[i], max)
}
return max
Copy the code
In the above solution, the current element is compared to the previous element, so if you keep a record, you don’t need any more comparisons
- Optimized solution, define a
dp[i]
Record a value of lengthi
The minimum value of the element at the end of the longest increasing subsequence dp[1]
Initialize thenums[0]
- if
dp
All of the elements in thenums[i]
, insert it to the end - Otherwise binary search dp, use
num[i]
Overwrite anything larger than it
const n = nums.length;
let max = 1
if(n <=1 )return n
const dp = [null, nums[0]]
for(let i = 1; i< n; i++){
if(dp[max] < nums[i]){
dp[++max] = nums[i]
}
// Binary search
let left = 1,
right = max,
mid,
pos = 0
while(left <= right){
mid = (right+left )>>1
if(dp[mid] < nums[i]){
/ / on the left
left = mid+1
pos = mid
}else{
right = mid-1}}// Replace the one larger than the current element
dp[pos+1] = nums[i]
}
return max
Copy the code
Conclusion: Dp is used to record the minimum value of the tail element of a longest increasing subsequence with length I, which can reduce the number of comparisons and optimize the time complexity O(nlogn).