哪里有做兼职的网站,室内设计师简历内容,网页设计策划案例,百度公司总部在哪里最长递增子序列 思路
定义状态#xff1a; 我们定义一个数组 dp#xff0c;其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化状态#xff1a; 对于数组中的每个元素 nums[i]#xff0c;初始时都可以被视为一个长度为1的递增子序列#xff0c;因此 dp[i] 的…最长递增子序列 思路
定义状态 我们定义一个数组 dp其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化状态 对于数组中的每个元素 nums[i]初始时都可以被视为一个长度为1的递增子序列因此 dp[i] 的初始值都设为1。状态转移方程 对于数组中的每个位置 i我们遍历它之前的所有位置 jj i。如果 nums[i] 大于 nums[j]说明 nums[i] 可以接在以 nums[j] 结尾的递增子序列后面形成一个更长的递增子序列。在这种情况下我们可以更新 dp[i] 为 dp[j] 1表示以 nums[i] 结尾的递增子序列长度是以 nums[j] 结尾的子序列长度加1。我们需要遍历所有 j i 的情况并取 dp[j] 1 中的最大值来更新 dp[i]。求解结果 在完成所有状态转移后dp 数组中的最大值就是最长递增子序列的长度。因为 dp[i] 存储的是以 nums[i] 结尾的最长递增子序列的长度所以最长递增子序列的实际长度可能不在数组末尾而是在数组中的某个位置。因此我们需要遍历整个 dp 数组来找到最大值这个最大值就是最长递增子序列的长度。优化空间复杂度 上述方法的空间复杂度是 O(n)因为我们需要一个大小为 n 的 dp 数组来存储状态。但实际上我们只需要知道前一个状态 dp[j] 的值来更新当前状态 dp[i]因此可以使用一个变量来替代整个数组从而将空间复杂度优化到 O(1)。实现细节 在实际编码时我们需要处理边界情况比如输入数组为空或只有一个元素的情况。在 main 方法中我们需要创建 LongestIncreasingSubsequence 类的实例并调用其 lengthOfLIS 方法来获取结果。
代码 import java.util.Scanner;
//给你一个整数数组nums
//找到其中最长严格递增子序列的长度
public class 最长递增子序列 {//写一个方法public int lengthOfLIS(int [] nums) {//在方法的开始我们首先处理边界情况if(numsnull || nums.length0) {return 0;}//dp[i]将存储以nums[i]结尾的最长递增子序列的长度。int[] dpnew int[nums.length];//初始化一个变量maxLength用于跟踪目前为止找到的最长递增子序列的长度int maxLength1;for(int i0;inums.length;i) {dp[i]1;//将dp[i]初始化为1因为任何元素都可以作为一个长度为1的递增子序列。for(int j0;ji;j) {//再用一个内层for循环遍历当前元素之前的所有元素。//在内层循环中我们检查当前元素nums[i]是否大于前面的元素nums[j]if(nums[i]nums[j]) {dp[i] Math.max(dp[i], dp[j]1);}}maxLengthMath.max(maxLength, dp[i]);}return maxLength;}public static void main(String[] args) {Scanner scan new Scanner(System.in);最长递增子序列 ss new 最长递增子序列();int [] nums {10,9,2,5,3,7,101,18};int result ss.lengthOfLIS(nums);System.out.println(result); }
}最长递增子序列的个数 代码
import java.util.Arrays;public class 最长递增子序列的个数 {public int findNumberOfLIS(int[] nums) {if(numsnull || nums.length0) {return 0;}int nnums.length;int[] dpnew int[n];//dp[i] 存储以 nums[i] 结尾的最长递增子序列的长度int[] count new int[n];//count[i] 存储以 nums[i] 结尾的最长递增子序列的个数Arrays.fill(count, 1);//初始化count数组每个元素的最长递增子序列至少包含一个元素int maxLength 1;//最长递增子序列的长度for(int i0;in;i) {dp[i]1;for(int j0;ji;j) {if(nums[i]nums[j]) {if(dp[j]1dp[i]) {//如果发现一个更长的递增子序列更新 dp[i] 并重置 count[i] dp[i]dp[j]1;count[i]count[j];}else if(dp[j]1dp[i]){count[i] count[j];}}}maxLength Math.max(maxLength, dp[i]);}int result0;for(int i0;in;i) {if(dp[i]maxLength) {resultcount[i];}}return result;}public static void main(String[] args) {最长递增子序列的个数 solutionnew 最长递增子序列的个数();int [] nums {1,3,5,4,7};int countsolution.findNumberOfLIS(nums);System.out.println(count);}}
知识点
Arrays.fill(count, 1); 是 Java 中的一个方法调用用于将数组 count 的所有元素设置为指定的值即 1。这个方法来自于 java.util.Arrays 类是一个静态工具类提供了很多用于操作数组例如排序、搜索、填充等的静态方法。
在这个特定的情境下Arrays.fill(count, 1); 被用来初始化 count 数组。由于我们正在计算最长递增子序列的个数每个元素至少可以作为一个长度为 1 的递增子序列的结束元素。因此count 数组的每一个位置都被设置为 1意味着每个元素开始时都被视为一个独立的递增子序列。
