本文共 731 字，大约阅读时间需要 2 分钟。

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]

输出: 4

解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

说明:可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。

你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

解题思路：动态规划解题

class Solution {
       public int lengthOfLIS(int[] nums) {
           // 对其判断        if(nums.length==0){
               return 0;        }        // 动态规划解题        int[] dp = new int[nums.length+1];        dp[0]    = 1;        // 结果记录        int maxLens = 1;        // 对其赋值        for(int i=1;i
   
    nums[j]){
                       // 记录状态更新                    dp[i] = Math.max(dp[i],dp[j]+1);                }            }            // 更新最大值            maxLens = Math.max(maxLens,dp[i]);        }        return maxLens;    }}
   

转载地址：http://nywdf.baihongyu.com/