matting

  • What is a subsequence?

Subsequence is a kind of new sequence derived from the “parent” sequence. The biggest characteristic is that it can be discontinuous. Note: discontinuous. Child string: is the product of a section cut from the parent string, its order, or in accordance with the order of the parent string to set; For example, String a1 = “123456”; String a2 = “456”; A2 is a subsequence of A1, String A3 = “1356”,a3 can be regarded as a subsequence of A1;

To the chase

  • 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].

  • The difficulty of medium

  • Bytedance interview appearances: 23;

  • Test array: {10, 9, 2, 5, 3, 7, 101, 18}

Their thinking

  • Look at the title, there is a word, please develop a thinking: is it dynamic planning?

  • Characteristics of dynamic programming topics:

    • Count type:
      • How many ways can I do STH
    • To find a maximum or minimum value:
      • Maximum ascending subsequence length
    • The search for existence (question: yes? Q: No?)
      • Can we pick k numbers so that the sum is sum

  • Step 1: Determine the status

// State array, in order to record the array, each index, there are at most a number of ascending subsequence; int [] dp = new int [length]; // Initialize the transition state, both are 1; Arrays.fill(dp,1);Copy the code
Ps: You might wonder, why not 0, if you look for an array that grows in reverse order, then there is no (0) increasing subsequence. Ha ha, this question is correct, indicating that you have used your brain to think, ok, please pay attention to, in the original problem example 3; Input: nums = [7,7,7,7,7] Input: 1, so, at least, return a 1;Copy the code
  • Step 2: State transition equation
    • Math.max() or math.min ();
    • Suppose {10, 9, 2, 5, 3, 7, 101, 18} is first taken to a range. If [10, 9, 2] is taken, we fix 2 and compare the sizes of 10, 9 and 2 respectively.
    • To ensure that nums[right] is greater than nums[left] compared with and, we decide whether to place its value in the current state of dp[left].
Ps: When I say fixed, it is a bit like sliding window. What is interesting is that after fixing a value, we will take all the values to the left of A and compare them with A. Let's have a look at the process of partial comparison:Copy the code
Original array: [10, 9, 2, 5, 3, 7, 101, 18]
0 times:nums[1]:9, NUMS [0]:10, current DP status: [1, 1, 1, 1, 1, 1]
———————————————————————
0 times:nums[2]:2, NUMS [0]:10, current DP status: [1, 1, 1, 1, 1, 1]
First:nums[2]:2, NUMS [1]:9, current DP status: [1, 1, 1, 1, 1, 1]
———————————————————————
0 times:nums[3]:5, NUMS [0]:10, current DP status: [1, 1, 1, 1, 1, 1]
First:nums[3]:5, NUMS [1]:9, current DP status: [1, 1, 1, 1, 1, 1]
Second:nums[3]:5, NUMS [2]:2, current DP status: [1, 1, 1, 2, 1, 1, 1]
———————————————————————
0 times:nums[4]:3, NUMS [0]:10, current DP status: [1, 1, 1, 2, 1, 1, 1]
First:nums[4]:3, NUMS [1]:9, current DP status: [1, 1, 1, 2, 1, 1, 1]
Second:nums[4]:3, NUMS [2]:2, current DP status: [1, 1, 1, 2, 2, 1, 1, 1]
Third time:nums[4]:3, NUMS [3]:5, current DP status: [1, 1, 1, 2, 2, 1, 1, 1]
———————————————————————
0 times:nums[5]:7, NUMS [0]:10, current DP status: [1, 1, 1, 2, 2, 1, 1, 1]
First:nums[5]:7, NUMS [1]:9, current DP status: [1, 1, 1, 2, 2, 1, 1, 1]
Second:nums[5]:7, NUMS [2]:2, current DP status: [1, 1, 1, 2, 2, 1, 1]
Third time:nums[5]:7, NUMS [3]:5, current DP status: [1, 1, 1, 2, 2, 3, 1, 1]
Fourth:nums[5]:7, NUMS [4]:3, current DP status: [1, 1, 1, 2, 2, 3, 1, 1]
———————————————————————
  • The bold part is the fixed value when we do the comparison;

code

  public int lengthOfLIS4(int[] nums) {
        int length = nums.length;
        if (length < 2) {
            return length;
        }
        int[] dp = new int[length];
        Arrays.fill(dp, 1);
        System.out.println(Arrays.toString(nums));
        for (int rightIndex = 1; rightIndex < length; rightIndex++) {
            System.out.println("| -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - |");
            for (int leftIndex = 0; leftIndex < rightIndex; leftIndex++) {
                // If the number on the right is greater than the number on the left, it is possible to do +1
                if (nums[rightIndex] > nums[leftIndex]) {
                    dp[rightIndex] = Math.max(dp[rightIndex], dp[leftIndex] + 1);
                }
                System.out.println("The first"+leftIndex+"Time."+"nums[" + rightIndex + "]:" + nums[rightIndex] + ", nums[" + leftIndex + "]:" +nums[leftIndex]+", current DP status:"+ Arrays.toString(dp)); }}// Iterate through the dp array, taking the maximum value
        int res = 0;
        for (int i = 0; i < length; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;
    }

Copy the code

I think

  • Debug and log are really useful for brush problems;

  • It’s really important to know who versus WHO when iterating through groups of numbers using a 2-level for loop…