300. 最长递增子序列

思路

1.定义dp数组

dp[i]表示：以数组下标为i的元素结尾的序列的最大长度为dp[i];

2.递推公式

if(nums[i]>nums[j]){        dp[i]=Math.max(dp[i]，dp[j]+1);}

即表示取下标为i的元素的之前的最大子序列。如果该最大子序列的最后一个元素比nums[i]小，则+1。

3.初始化

根据定义dp数组的每个元素的下标都为1；

4.遍历顺序

根据递推公式可以知道是正序遍历

5.打印dp数组

取dp数组中最大的元素即可。

代码

class Solution {    public int lengthOfLIS(int[] nums) { int dp[] = new int[nums.length]; Arrays.fill(dp,1); for(int i =1;i<nums.length;i++){     for(int j=0;jnums[j]){      dp[i]=Math.max(dp[i],dp[j]+1);  }     }    } int res = 0; for (int i = 0; i < dp.length; i++) {     res = Math.max(res, dp[i]); } return res;    }}