【Hot100】LeetCode—300. 最长递增子序列

• 原题链接：300. 最长递增子序列

1- 思路

题目识别

• 识别1 ：给出一个数组输入 nums
• 识别2：严格递增的子序列，子序列可以是不连续的

动规五部曲

思路：

• 1- 定义 dp 数组
  • dp[i] 代表长度为 i 的数组的最长递增子序列的长度
• 2- 递推公式
  • if(nums[j] > nums[i]) 则更新 dp[j] = Math.max(dp[i] + 1,dp[j])

2- 实现

⭐最长递增子序列——题解思路

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len+1];

        // 2.递推公式
        // if(nums[i] > nums[j]) dp[j] = dp[i] + +1;

        // 初始化
        Arrays.fill(dp,1);

        for(int i = 1 ; i <= len;i++){
            for(int j = 1 ; j < i ; j++){
                if(nums[i-1] > nums[j-1]){
                    dp[i] = Math.max(dp[j] + 1,dp[i]);
                }
            }
        }
        int res = 1;
        for(int i : dp){
            res = Math.max(i,res);
        }
        return res;
    }
}

3- ACM 实现

public class maxLenSub {

    public static int findMax(int[] nums){
        //1.定义 dp
        int len = nums.length;
        int[] dp = new int[len+1];

        // 2. 递推公式
        // if(nums[i] > nums[j])

        // 3.初始化
        Arrays.fill(dp,1);

        for(int i = 1 ; i <= len;i++){
            for(int j = 1 ; j < i ; j++){
                if(nums[i-1] > nums[j-1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 1 ;
        for(int r:dp){
            res = Math.max(res,r);
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.replace("[","").replace("]","");
        String[] parts = input.split(",");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < nums.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }
        System.out.println("结果是"+findMax(nums));
    }
}