怎么用php做网站,中国企业网信息网,大连工程建设信息网,wordpress 商品 模板下载题目描述
给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 …题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例
示例1
输入nums [10,9,2,5,3,7,101,18]
输出4
解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例2
输入nums [0,1,0,3,2,3]
输出4示例3
输入nums [7,7,7,7,7,7,7]
输出1思路
定义dp[i]表示以第i个元素为结尾的最长上升子序列的长度。
代码如下 public int lengthOfLISNormal1(int[] nums) {int n nums.length;if(n 0 || n 1) return n;// dp[i]表示以第i个元素为结尾的最长上升子序列的长度。int[] dp new int[n];Arrays.fill(dp, 1);int res 1;for(int i 1;i n;i){for(int j 0;j i;j){if(nums[i] nums[j]){// dp[j] 1 表示在以 nums[j] 结尾的上升子序列的末尾添加当前元素// nums[i] 后得到的新的上升子序列长度为 dp[j] 1。因为当前元// 素 nums[i] 可能可以添加到以 nums[j] 结尾的上升子序列中所以需// 要比较加入当前元素后子序列的长度是否更长如果更长则更新当前// dp[i] 的值。dp[i] Math.max(dp[i],dp[j] 1);}}res Math.max(res, dp[i]);}return res;}输出最长递增子序列
代码1 public ListInteger printLengthOfLISNormal(int[] nums) {int n nums.length;// dp[i]表示以第i个元素为结尾的最长上升子序列的长度。ListInteger[] dp new List[nums.length];for (int i 0; i n; i) {dp[i] new ArrayList();}dp[0].add(nums[0]);for(int i 1;i n;i){int index -1, maxLen 0;for(int j 0;j i;j){if(nums[i] nums[j] dp[j].size() maxLen){maxLen dp[j].size();index j;}}if(index ! -1){dp[i].addAll(dp[index]);}dp[i].add(nums[i]);}ListInteger res dp[0];for (int i 1; i dp.length; i) {if (res.size() dp[i].size()) {res dp[i];}}return res;}代码2 public ListInteger printLengthOfLISNormal1(int[] nums) {int n nums.length;int[] dp new int[n]; // dp[i]表示以第i个元素为结尾的最长上升子序列的长度Arrays.fill(dp, 1); // 初始时每个元素自成一个子序列int maxLength 1, endIndex 0; // 记录全局最长子序列的长度和结束位置for (int i 1; i n; i) {for (int j 0; j i; j) {if (nums[i] nums[j]) {dp[i] Math.max(dp[i], dp[j] 1);// 更新全局最长子序列的信息if (dp[i] maxLength) {maxLength dp[i];endIndex i;}}}}// 根据全局最长子序列的长度和结束位置回溯构造最长上升子序列ListInteger res new ArrayList();for (int i endIndex; i 0; i--) {if (dp[i] maxLength) {res.add(nums[i]);maxLength--;}}Collections.reverse(res); // 因为是逆序添加的需要翻转一下得到正确顺序return res;}