【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.定义 dpint 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));}
}

---