This is the 15th day of my participation in Gwen Challenge. For more information, see: Gwen Challenge 😄


  \color{red}{~}

A

Leecode 300. Longest increasing subsequence

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] and therefore has a length of 4.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Example 3:

Input: nums = [7,7,7,7,7]

Output: 1.

Tip:

1 <= nums.length <= 2500

-104 <= nums[i] <= 104

Advanced:

Can you design a solution with O(n2) time?

Can you reduce the time complexity of the algorithm down to order n log n?

—

❤ ️ ❤ ️ ❤ ️ ❤ ️

2.1. Dynamic planning component 1: State determination

To put it simply, when solving dynamic programming, you need to open an array. What does each element of the array f[I] or f[I][j] represent, similar to what x, y, and z represent in mathematical problems

The last step

We define dp[I] as the length of the longest ascending subsequence ending in the ith digit, considering the first I elements

Max {d[I], d[j] +1, Max {d[I] +1, Max {d[I], d[j] +1}

The final step, such as nums = [0,1,0,3,2,9], is to match the preceding number with the 9 block, find the number less than I, and record the occurrence

1.2. Dynamic programming component 2: Transfer equation

dp[i] = Math.max(dp[i], dp[j] + 1);

1.3. Dynamic programming component 3: initial conditions and boundary cases

dp[0] = 1;

int maxans = 1; // The minimum time

1.4. Dynamic programming component 4: Order of calculation

Each I matches the preceding 0 to I -1


Great! 😄 😄 😄 \ color {green} {! 😄 😄 😄 ~}

Reference code

Java version

  class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxans = 1;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxans = Math.max(maxans, dp[i]);
        }
        returnmaxans; }}Copy the code

Thank you for reading this, if this article is well written and if you feel there is something to it

Ask for a thumbs up 👍 ask for attention ❤️ ask for share 👥 for 8 abs I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much! ❤ ️ ❤ ️ ❤ ️ ❤ ️