给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]输出：1
提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
思路：
1）dp[i]的下标及含义
- 第i个数的最大子序列长度为dp[i]；
2）递推公式
- 我们的dp[i]可以由前面的某个值推导出来，注意是前面的某个值。而不是前面的这个值。
if (dp[i] > dp[j]) dp[i] = Math.max(dp[i], dp[j] + 1)
dp[i]和前面的 一个数比完，值就会改变，所以要和dp[j] + 1取最大值。 - 如果这个数都比前面的小，那就没必要处理了，让它保持原值就行，反正最后结果都会把它过滤掉。
3）数组初始化
- 都为1就行
4）遍历顺序
- 从前往后
5）举例推导
- 在纸上写出来
代码
1 class Solution {
2 public int lengthOfLIS(int[] nums) {
3 int len = nums.length;
4 // 边界条件处理
5 if (len == 1) return 1;
6 int[] dp = new int[len];
7 // 初始化dp数组
8 // 每一个位置的初始值都应该为1
9 Arrays.fill(dp, 1);
10 dp[0] = 1;
11 for (int i = 1; i < len; i++) {
12 for (int j = 0; j < i; j++) {
13 if (nums[i] > nums[j]) {
14 // 注意这里，不是由前面一个数推导出来的，而是前面的某个数，只要大于前面某个数，那就+1来比较
15 // dp[i]每和前面一个数比完，都会变化，所以要取最大值
16 dp[i] = Math.max(dp[i], dp[j] + 1);
17 }
18 }
19 }
20 int result = 0;
21 for (int i = 0; i < dp.length; i++) {
22 result = result > dp[i] ? result : dp[i];
23 }
24 return result;
25 }
26
总结
- 不要局限了自己的思想，被以前的经验束缚住。比如本题，得跳出去，不是由前一个数推导来的，而是前面某个数。