给定一个长度为 n 的数组 arr,求它的最长严格上升子序列的长度。
所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的,当且仅当该序列不存在两个下标 和 满足 且 。
数据范围:
要求:时间复杂度 , 空间复杂度
[6,3,1,5,2,3,7]
4
该数组最长上升子序列为 [1,2,3,7] ,长度为4
public int LIS (int[] arr) { //上升子序列,不连续,需要判断大小 int[] dp=new int[arr.length]; Arrays.fill(dp,1); if(arr.length==1) return 1; int ans=0; for(int i=1;i<arr.length;i++){ for(int j=0;j<i;j++){ if(arr[j]<arr[i]){ dp[i]=Math.max(dp[i],dp[j]+1); } } ans=Math.max(ans,dp[i]); } return ans; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { if(arr.length == 1){ return 1; } int[] dp = new int[arr.length]; Arrays.fill(dp,1); int res = 0; for(int i=1;i<arr.length;i++){ for(int j=0;j<i;j++){ if(arr[i]>arr[j] ){ dp[i] = Math.max(dp[i],dp[j]+1); } if(dp[i]>res){ res = dp[i]; } } }return res; // write code here } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { //特殊情况考虑 int len = arr.length; if(arr==null || len==0){ return 0; } //dp[i]:表示arr以i为结尾的最长上升子序列的个数 //很明显dp初始的值是1,在计算过程中顺便记录最大值的情况 //j的遍历是:i之前的所有以j为结尾的最长上升子序列的个数 也就是当前的数值arr[i] > arr[j],那么是从arr[j]过来呢还是直接从arr[i]开始呢 int[] dp = new int[len]; Arrays.fill(dp,1); int max = 1; for(int i=1;i<len;i++){ for(int j=0;j<i;j++){ if(arr[i] > arr[j]){ dp[i] = Math.max(dp[j]+1,dp[i]); max = Math.max(max,dp[i]); } } } return max; } }
public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { int len = arr.length; if(len == 0) return 0; int[] dp = new int[arr.length]; // 初始化dp数组 值都为1,即每个数针对于自己本身而言,上升序列都为1 Arrays.fill(dp, 1); // 记录最大上升序列 int max = 1; // 遍历数组,下边从1开始,即数组第二个元素,因为第一个元素固定为1 for (int i = 1; i < arr.length; i++) { // 小循环倒序遍历,从i-1开始 到 0结束, // 即每次都将判断 序列以i结尾的元素. // 向前查找,比arr[i]小的元素,得到它们的dp数组记录上升序列的个数 + 1,与dp[i] 取最大值即为当前i索引位置 最大上升序列 for (int j = i - 1; j >= 0; j--) { if(arr[i] >= arr[j]){ dp[i] = Math.max(dp[j] + 1, dp[i]); } } // 内循环结束,说明以i结尾的上升序列个数已经找到 并存入ap[i]中,然后每次与之前记录的max作比较,取最大值 max = Math.max(dp[i], max); } // 外层循环结束,max即为解 return max; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // write code here int[] dp = new int[arr.length]; Arrays.fill(dp, 1); int res = 0; for (int i = 0; i < arr.length; i ++) { for (int j = i + 1; j < arr.length; j ++) { if (arr[j] > arr[i]) { dp[j] = Math.max(dp[j], dp[i] + 1); } res = Math.max(res, dp[j]); } } return res; } }
import java.util.*; public class Solution { public int LIS (int[] arr) { if(arr.length==0){ return 0; } // dp 表示以它为底的最长序列的长度 int res=1; int[] dp=new int[arr.length]; dp[0]=1;// 初始化 for(int i=1;i<dp.length;i++){ int max=1; for(int j=0;j<i;j++){ if(arr[i]>arr[j]){ //说明可以查看,到达最大长度 max=Math.max(dp[j]+1,max); } } dp[i]=max; res=Math.max(max,res); } return res; } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // write code here if(arr.length==0){return 0;} if(arr.length==1){return 1;} int[] dp=new int[arr.length]; dp[0]=1; for(int i=1;i<=arr.length-1;i++){ int max=0; for(int j=i-1;j>=0;j--){ if(arr[j]<arr[i]){ max=Math.max(max,dp[j]); } } dp[i]=max+1; } return max(dp); } public int max(int[] arr){ int max=arr[0]; for(int i=1;i<arr.length;i++){ max=arr[i]>max?arr[i]:max; } return max; } }
import java.util.*; public class Solution { public int LIS (int[] arr) { //dp[i]表示以下标i结尾的最长递增子序列的长度 int[] dp = new int[arr.length]; //dp数组初始化为1,因为以每个位置结束最长递增子序列至少包括自己 Arrays.fill(dp, 1); for (int i = 0; i < dp.length; i++) { for (int j = 0; j < i; j++) { //取当前位置之前的最大值递增子序列长度的最大值。 if (arr[j] < arr[i]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } } //找出dp数组中的最大值 int res = 0; for (int item : dp) { res = Math.max(res, item); } return res; } }
//赋1的操作没必要单独做,可以在循环的时候顺便完成 public int LIS (int[] array) { int[] f = new int[array.length]; int ans = 0; for(int i=0; i<array.length; ++i) { f[i]=1; //f[i]=max{1, max{f[j]+1, 0=<j<i,array[i]>array[j]}} for(int j=0; j<i; ++j) { if(array[i]>array[j]) f[i]=Math.max(f[i], f[j]+1); } //ans = max{f[i], 0=<i<n} ans = Math.max(f[i], ans); } return ans; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // write code here int len = arr.length; int[] dp = new int[len + 1]; Arrays.fill(dp,Integer.MAX_VALUE); dp[0] = Integer.MIN_VALUE; for(int i = 0; i < len; i++){ for(int j = i; j >= 0; j--){ if(arr[i] > dp[j]){ dp[j + 1] = Math.min(dp[j + 1],arr[i]); } } } int res = 0; for(int i = 1; i <= len ; i++){ if(dp[i] >= Integer.MAX_VALUE ){ break; }else{ res = i; } } return res; } }
public int LIS (int[] arr) { // write code here if(arr.length==0) return 0; if (arr.length==1) return 1; //dp代表以这个当前下标结尾的最长子序列 int[] dp=new int[arr.length]; //base case //最开始忘记初始化2-n的元素都是1了,结果错了,看了评论才发现 dp[0]=1; dp[1]=arr[1]>arr[0]?2:1; //这里要注意一下,因为最开始的时候,每一个数单独都可以构成一个上升子序列,所以要初始化为1 for (int j=2;j<dp.length;j++) dp[j]=1; int maxlen=dp[0]; for (int j=2;j<dp.length;j++){ for (int i=0;i<j;i++){ if (arr[i]<arr[j]){ dp[j]=Math.max(dp[j],dp[i]+1); } } maxlen=Math.max(dp[j],maxlen); } return maxlen; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // write code here int n = arr.length; if(n == 0) return 0; int[] dp = new int[n]; // dp[i]表示以arr[i]结尾时的最长递增子序列长度 Arrays.fill(dp, 1); int maxLen = 1; for(int i = 1; i < n; i++){ for(int j = i - 1; j >= 0; j--){ if(arr[j] < arr[i]){ // arr[j] < arr[i],可以把arr[i]接在arr[j]后面,构成长度为dp[j]+1的递增子序列 dp[i] = Math.max(dp[i], dp[j] + 1); // 选择能构成更长递增子序列的arr[j] } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; } }