Longest strictly increasing subsequence

introduce

Given an array arr, return arr The length of the longest strictly increasing subsequence of

Subarray is continuous , such as [1,3,5,7,9] The subarrays of are [1,3],[3,5,7] wait , however [1,3,7] It's not a subarray .

  Example :
    Input : [10,9,2,5,3,7,101,18]
    Output : 4
   explain :  The longest ascending subsequence is  [2,3,7,101], Its length is  4.

How to solve the problem

Using the idea of dynamic programming , use i Traversal array , And then use j Ergodic less than i The data of , If i The data of is greater than j And dp[i] The length of is less than dp[j]+1 The length of , Then write it down ;
In fact, I know how to solve problems and the recurrence formula , It's easy to write ,
$$D(x)=\{\begin{array}{ll}max(dp[j]+1,dp[i]),& 0<=j<iAndarr[j]<arr[i]\\ 1,& 0<=j<iAndarr[j]>arr[i]\end{array}$$

java Code

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]);
        }
        return maxans;
    }
}

Complexity analysis

• Time complexity ：$O(n^2)$, among n Is an array nums The length of . The number of states of dynamic programming is n, Calculation state dp[i] when , need O(n) Time traversal $dp[0\dots i-1]dp[0\dots i-1]$ All states , So the total time complexity is $O(n^2)$

• Spatial complexity ：$O(n)$, Additional length required is n Of dp Array .