Make writing a habit together! This is the fourth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

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

Longest increasing subsequence.

Two, the title requirements

Sample 1

Input: nums = [10,9,2,5,3,7,101] output: 4 explanation: the longest increasing subsequence is [2,3,7,101], so length is 4.Copy the code

The sample 2

Input: nums = [0,1,0,3, 3] Output: 4Copy the code

inspection

1. Subsequence and dynamic programming 2. 15 to 35 minutes is recommendedCopy the code

Third, problem analysis

For this one can use dynamic programming, binary search solution, dynamic programming although the execution time is more, but it is easier to understand, so use dynamic programming to complete this problem.

Remember our previous three-step strategy for dynamic planning? The previous dynamic planning exercises are equivalent to getting started. If you do not know dynamic planning, you can try to start from this introductory problem solution:

Day 34: The frog jumps the steps and starts to make a start.

Again, with our three-step strategy:

Step 1: Understand what it means

This is a one-dimensional dynamic programming, in which DP [I] represents the maximum length of the subsequence with the ith subscript as the endpoint.

Step 2 Variable initialization:

At the beginning of the variable, for each dp[I], the worst that can happen is that all the preceding numbers are greater than I, and then it’s just a single 1.

The third step:

Before determining the value of dp[I], we should know the value of dp[0~ I -1].

Define j = I - 1

Nums [I] = nums[j] = nums[I] = nums[j] = nums[I] = nums[j]

dp[i]=dp[j]+1; (The added 1 is nums[I]).

Dp [I] initializes 1 as long as nums[I]>nums[j], then we can compare the size

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

Three steps, call it a day!

Four, coding implementation

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int i,j,n=nums.size(),dp[n+2],ans=0;// Initialize variables
        for(i=0; i<n; i++)The I / / cycle
        {
            dp[i]=1;// The variable is initialized
            for(j=0; j<i; j++)// Iterate over the number before I
            {
                if(nums[j]<nums[i])// If I is larger than j
                    dp[i]=max(dp[j]+1,dp[i]);//nums[I] joins the family
            }
            ans=max(ans,dp[i]);// Find the maximum value
        }
        return ans;// Return the result}};Copy the code

V. Test results