“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

Given an integer array nums, find the length of the longest strictly increasing subsequence.

A subsequence is a sequence derived from an array that deletes (or does not delete) the elements of the array without changing the order of the rest of the elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1: input: nums = [10,9,2,5,3,7,101,18] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.

Example 2: Input: nums = [0,1,0,3, 3] Output: 4

Example 3: Input: nums = [7,7,7,7,7] Output: 1

Tip:

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 104

Their thinking

Dynamic programming

This problem we should change numerous for brief, don’t consider to think about whether to choose the location on each position of the value added to the sequence of the eldest son, because it need to record before choosing the value of the contrast comparison, thinking also not clear, complex also lost the advantage of dynamic programming, we do reasoning value at a certain position in the brain, when the end of the sequence His longest sequence length is derived from the longest sequence value less than the ith position value + 1. And then we choose the maximum from the longest increasing subsequence length at each end, which is the longest increasing subsequence length.

  1. The definition of dp [I]

Dp [I] represents the length of the maximal sequence in which the i-th number is chosen as the end of the preceding i-number

  1. State transition equation

The last sequence of the i-th terminator is equal to the maximum value of dp + 1 at positions j from 0 to i-1.

So the recursive formula is: the if (nums [I] > nums [j]) dp [I] = Max (dp [I], dp [j] + 1);

Note that instead of comparing dp[I] with dp[j] + 1, we want to take the maximum value of dp[j] + 1.

  1. Initialization of dp[I]

For each I, the corresponding dp[I] (i.e. the length of the i-th terminator of the sequence) starts at least 1, because each chooses itself as the terminator of the sequence.

  1. Determine the traversal order

Dp [I] is derived from the longest ascending subsequence from 0 to i-1, so traversing I must be traversing from front to back.

Therefore, we can record the longest increasing subsequence length by comparing the dp values when updating them

var lengthOfLIS = function(nums) {
    let len = nums.length;
    let dp = new Array(len).fill(1);
    let res = 1;
    for (let i = 1; i < len; i++) {
        for (let j = 0; j < i; j++) {
            if(nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i],dp[j] + 1); }}if(dp[i] > res) res = dp[i];
    }
    return res;
};
Copy the code