题目描述:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| class Solution { public int lengthOfLIS(int[] nums) { if (nums.length <= 1) { return nums.length; } int[] dp = new int[nums.length]; for (int i = 0; i < nums.length; 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); } } } int res = 0; for (int i = 0; i < nums.length; i++) { res = Math.max(res, dp[i]); } return res; } }
|