300. 最长递增子序列 -Java 动态规划

原题地址：https://leetcode.cn/problems/longest-increasing-subsequence/

题解

设dp[i]为以nums[i]结束的最长子序列长度

让j遍历[0,i]，当nums[j]<nums[i]时表示以nums[j]结束的子序列可以再加上一个nums[i]成为一个更长的子序列

• 此时该子序列的最长长度=dp[j]+1

用dp[i]维护j遍历过程中的子序列长度的最大值

if(nums[j]<nums[i]&&dp[j]+1>dp[i]){
    dp[i]=dp[j]+1;
}

在j遍历结束后dp[i]即为以nums[i]结束的最长子序列长度，返回dp数组中的最大值即可

优化：

当j遍历到j+1<dp[i]时，nums[0]——nums[j]的长度+1小于当前dp[i]的值

此时即便nums[i]可以与以nums[j]结束的子序列结合，结合出来的子序列长度也不会比当前的dp[i]更大，因此已无遍历价值

当j+1<dp[i]时，即可跳出循环

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        int max=0;
        for(int i=0;i<nums.length;i++){
            dp[i]=1;
            for(int j=i;j>=0&&j+1>=dp[i];j--){
                if(nums[j]<nums[i]&&dp[j]+1>dp[i]){
                    dp[i]=dp[j]+1;
                }
            }
            if(max<dp[i])max=dp[i];
        }
        return max;
    }
}