300. 最长上升子序列

image.png

解题思路

先好好看题，最大上升序列，说明不连续也可以
基本思路：
dp[i]来表示前i个元素中最大的子序列的个数
1：遍历nums数组
2：遍历nums[j]之前的所有元素
（1）如果nums[j]>nums[k] 带入状态转移方程Math.max(dp[j],dp[k]+1))
3：对dp数组排序，选一个最大的值返回
其余看注释

代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        if(nums.length==0) return 0;
        int l=nums.length;
        int [] dp=new int[l];//dp[i]来表示前i个元素中最大的子序列的个数
        for(int i=0;i<l;i++){
            dp[i]=1;//给dp初始化为1，符合后面的比较，因为一个元素本身就是一个长度为1的子序列
        }
        for(int j=0;j<l;j++){//遍历整个数组
            for(int k=0;k<j;k++){//遍历第j个元素之前的元素
                if(nums[j]>nums[k]) dp[j]=Math.max(dp[j],dp[k]+1);//状态转移方程，比较1和dp[k]+1,dp[k]+1代表遍历j元素之前的k元素，///选其状态，并加1
            }
        }
        Arrays.sort(dp);//给dp数组排序选一个最大的
        return dp[l-1];
    }
}