LC.300-最长递增子序列长度题解

public class LongestIncreaseLength {
    public int lengthOfLIS(int[] nums) {
        //单串问题
        if(nums==null || nums.length==0){
            return 0;
        }
        int res=-1;
        int dp[]=new int[nums.length];
        dp[0]=1;
        for(int i=0;i<nums.length;i++){
            int MaxLen=1;//因为对于单个元素无论如何最低都是1了
            for(int j=0;j<i;j++){//搜索前面O(n)种情况，因为他是不连续的，可以从前面的i个种作为他的上一个元素
                if(nums[i]>nums[j]){//符合递增特点
                    MaxLen=Math.max(dp[j],MaxLen);
                    dp[i]=MaxLen+1;
                    //在递增特性中符合的选择最长序列并基础上加一
                }
            }
            res=Math.max(dp[i],res);//刷新最大值
        }
        return res;//返回最大值
    }
}

这个是一个DP的单串问题，前置状态属于前O(n)个状态型，需要在前O(n)个状态中取最小值
dp公式:DP[n]=min(DP[n-1]...DP[0])+1 && nums[i]>nums[j]
时间复杂度为O(n^2);