Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Topic describes

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,7] Output: 1 source: LeetCode Link: https://leetcode-cn.com/problems/longest-increasing-subsequence copyright belongs to The Collar network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Thinking summary

• Today’s algorithm problem is to find the length of the longest strictly increasing subsequence.
• Dynamic programming is adopted to solve the problem: the value of dp[I] represents the longest sequence length of I digits before NUMs. The initial value dp[I] is 1.
• The interval 0 to i-1 is then iterated each time, and nums[I] is compared to the size, dynamically updating the maximum value of dp[I]. The code is as follows:

Through the code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ans = 0;
        if (n == 0) {
            return ans;
        }

        int[] dp = new int[n];
        dp[0] = 1;
        ans = 1;
        for (int i = 1; i < n; 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);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
Copy the code

conclusion

• The time complexity of the above algorithm is O(n * n), the space complexity is O(n).
• Adhere to the algorithm of the day, come on!