首页 > 其他分享 >300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

时间:2022-11-30 10:33:21浏览次数:43  
标签:nums 300 max len int Subsequence Output Input Increasing

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore 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

 

class Solution {

    public int lengthOfLIS(int[] nums) {

       int n = nums.length, 

       int max_len = 0;

       int[] len = new int[n];

       for(int i = 0; i < n; i++) {

          len[i] = 1;           

          for(int j = 0; j < i ; j++) {//对每一元素,都从第一个元素开始与它比较

              if(nums[i] > nums[j]) {                

                 if(len[i] < len[j] + 1) 

                    len[i] = len[j] + 1;                                     

             }

          }          

          if(max_len < len[i]){

              max_len = len[i];              

          }

       }

       return max_len;   

   }

}

标签:nums,300,max,len,int,Subsequence,Output,Input,Increasing
From: https://www.cnblogs.com/MarkLeeBYR/p/16937670.html

相关文章