[编程题] lk [300. 最长上升子序列-动态规划]

[编程题] lk 300. 最长上升子序列-动态规划

题目

输入输出

注意的问题

这里说的是上升的可以是非连续的子序列的最长长度，可以采用动态规划来做。

思想：

转移方程：

​ 我们在某点nums[i] 只要看其前边的0~i-1个比nums[i]小的数的最大dp[j]值。

那么，到dp[i] 的值就是在0~i-1范围的max(dp[j]+1) 、故此处涉及到两层for循环。

方法1：动态规划

class Solution {

    //方法1:动态规划
    public int lengthOfLIS(int[] nums) {
        //极端条件
        if(nums==null || nums.length==0) {return 0;}

        int max=1;
        int n = nums.length;
        int[] dp = new int[n];
        for(int i=0;i<n;i++){dp[i]=1;}  //最少每个元素的上升子序列是1

        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    //解释：在nums[i]前查看所有比nums[i]小的值的dp值，加1是到nums[i]这里本身也算一步
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
            }
            //每次更新此dp[i]就纪录最大值
            max = Math.max(dp[i],max);
        }
        return max;
    }
}