东莞专业的网站推广价格,wordpress存放的目录在,wordpress物流主题,seo关键词推广渠道300.给你一个整数数组 nums #xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[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设 dp[i] 为以 nums[i] 结尾的最长子序列的长度这时就不是简单的根据 dp[i-1] 推导因为这个子序列是从前面任何一点连接过来的比如 […,7,6,9]我这个子序列可能是 [ …,7,9] 也可能是 […,6,9]所以我们要取最大的情况 public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];Arrays.fill(dp,1);int max 1;for(int i1;inums.length;i){// 往前面所有点找如果有小于 i 点的说明可能是从 j 连接到 i 的子序列for(int ji-1;j0;j--){if(nums[i]nums[j])dp[i]Math.max(dp[j]1,dp[i]);}// 取 dp[] 中的最大值不一定是以 nums 尾部结尾的子序列长度最长max Math.max(dp[i],max);}return max;}还有个 dp 贪心 二分查找的思路比如两个递增子序列 [1,2,3] 和 [1,2,4]我们会觉得哪个更好应该是前者因为它的尾端元素更小有更大的可能延长下去所以我们定义 dp[i] 为长度为 i1 的递增子序列的尾部最小取值我们初始化 dp[0] 为 nums[0]在遍历过程中只会遇到两种情况nums[i] 大于 dp 尾部元素那么就把 nums[i] 加在 dp 数组末尾nums[i] 小于 dp 尾部元素那么就把 nums[i] 替换掉最先大于 dp 数组中的某个数比如数组 [0,3,1,6,2,2,7,8]的遍历过程 dp[0] 0dp[1] 3此时子序列为 03这时我们找到了更好的子序列所以替换 dp[1] 为 1dp[2] 6此时子序列为 016我们又找到了更好的子序列所以替换为 dp[2] 为 2跳过dp[3] 7dp[4] 8 最终我们能得到最长递增子序列 01678值得注意的是在遍历过程中dp 数组并不表示一个完整的递增子序列这也和我们的定义有关因为我们只关心递增子序列的尾部元素所以我们能保证的只是 dp[i] 这一个数是长度为 i1 的递增子序列的尾部最小取值情况下的尾部元素而上面的例子只是恰好每次都替换了尾部元素使得 dp 数组一直能表示一个子序列。比如数组 [1,2,4,3] 只包含 2 个长度为 3 的子序列 123 和 124我们只保证 dp[2] 是长度为 3 的最优(尾部元素最小)的递增子序列 123 的尾部元素 3。比如数组 [3,5,6,2] 我们会得到 dp 数组为 [2,5,6]但并不存在子序列 256他们只表示长度为 1 的最优子序列为 2长度为 2 的最优子序列为 x5长度为 3 的最优子序列为 xx6管他 x 是几我们只要得到最后子序列的长度就好 public int lengthOfLIS(int[] nums) {int[] dp new int[nums.length];dp[0] nums[0];int index 0;for(int i1;inums.length;i){// 大于就添加到 dp 数组尾部if(nums[i]dp[index])dp[index]nums[i];// 小于就替换 dp 数组中最接近且大于它的数else binaryReplace(dp,index,nums[i]);}return index1;}// 用二分法把小于 dp 数组尾端元素的 nums[i] 替换到 dppublic void binaryReplace(int[] dp,int index,int n){int left 0, right index;while(leftright){int mid left(right-left)/2;if(dp[mid]n)return;else if(dp[mid]n)left mid1;else right mid-1;}dp[left]n;}
