输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
解析1:动态规划。
class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0){ return 0; } int res = 0; int[] dp = new int[nums.length]; Arrays.fill(dp, 1); for(int i = 0;i < nums.length;i++){ for(int j = 0;j < i;j++){ if(nums[j]<nums[i]){ dp[i] = Math.max(dp[j]+1,dp[i]);//j<i可以保证不连续的之前有值小于当前值 } } res = Math.max(res,dp[i]); } return res; } }