LeetCode 300. Daily question of the longest increasing subsequence

Problem description

Give you an array of integers nums , Find the length of the longest strictly increasing subsequence .

Subsequence   Is a sequence derived from an array , Delete （ Or do not delete ） Elements in an array without changing the order of the rest . for example ,[3,6,2,7] It's an array [0,3,1,6,2,2,7] The subsequence .

 
Example 1：

Input ：nums = [10,9,2,5,3,7,101,18]
Output ：4
explain ： The longest increasing subsequence is [2,3,7,101], So the length is 4 .
Example 2：

Input ：nums = [0,1,0,3,2,3]
Output ：4
Example 3：

Input ：nums = [7,7,7,7,7,7,7]
Output ：1
 

Tips ：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-increasing-subsequence
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 1) return 1;
        int[] dp = new int[n];
        dp[0] = 1;
        int ans = 0;
        for(int i = 1;i < n;i++){
            dp[i] = 1;
            for(int j = 0;j < i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
}