目录
- 1- 思路
- 题目识别
- 动规五部曲
- 2- 实现
- ⭐最长递增子序列——题解思路
- 3- ACM 实现
- 原题链接: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));}
}