给定一个长度为 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
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; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { // write code here vector<int>res; int len = arr.size(); for(int i=0;i<len;i++){ if(res.size() == 0 || res.back() < arr[i]){ res.push_back(arr[i]); }else{ int j = res.size()-2; while(j>=0){ if(arr[i] > res[j])break; j--; } res[j+1] = arr[i]; } } return res.size(); } };
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; } }
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; } // dp[i] - 表示以i位置元素为结尾的最长严格上升子序列的长度 // i - 从0(左)往n(右)推 int[] dp = new int[arr.length]; // 初始化dp // 当只有0位置元素时,上升子序列仅有其自己,故长度为1 dp[0] = 1; // 递推dp int result = 1; for (int i = 1; i < arr.length; i++) { int max = 1; // 求解dp[i],观察dp[0 ~ i-1]的所有位置,若有小于arr[i]的,就尝试让arr[i]接在其后面,+1 for (int j = 0; j < i; j++) { // 先假设以arr[j]为结尾的最长严格上升子序列只有它自己 int length = 1; if (arr[j] < arr[i]) { // arr[i]可以接在以arr[j]为结尾的最长上升子序列后面 length = dp[j] + 1; } // 更新max if (length > max) { max = length; } } // 根据max记录dp[i] dp[i] = max; // 更新最终的结果,及所有位置中最大的那个值 if (dp[i] > result) { result = dp[i]; } } return result; } }
public int LIS(int[] arr) { // write code here int len = arr.length; if (len == 0) return 0; if (len == 1) return 1; // dp 表示截止到当前的上升子数组的最大值 int[] dp = new int[len]; dp[0] = 1; int maxLen = 1; for (int i = 1; i < len; i++) { // 每次开始的地方都要初始化为1 dp[i] = 1; // 对 [j,i) 进行查找, dp[i] 记录其全局最大值 /* * 因为 dp[i] = Math.max(dp[i], dp[j] + 1); * 在计算的时候 j = 2 时,则可能是 dp[2] +1, * 在 j=3 时,可能是 dp[3]+1, 而 dp[2] 和 dp[3] 的值在 i =2和 i=3 的时候已经计算过了, * 即使 arr[2] > arr[3], 我们在更新 i = 5 时的 dp[i] 的值时,也会取其较大值, * 因此整个遍历过程中,计算 dp[5]时,我们会在 dp[0~4] 之间找到一个最大值, * 并根据 arr[5] 的大小判断是否要 +1 */ for (int j = 0; j < i; j++) { // 找到一种,对于 dp[j] 来讲,多了一个元素 if (arr[i] > arr[j]) { // 此时的 dp[j] 早已在之前的循环中计算好了 dp[i] = Math.max(dp[i], dp[j] + 1); } } maxLen = Math.max(maxLen, dp[i]); } return maxLen; }
int n = arr.length; int[] res = new int[n]; int end = -1; for(int i = 0; i < n; i++) { if(i == 0 || res[end] < arr[i]) { res[++end] = arr[i]; }else { int index = binarySearch(res, end, arr[i]); // 更新数组的时候,只有最长的递增子串才可能突破 res 的长度 // 例如: {25,26,27,1,2,3,4,5}, 到 arr[i] == 3 的时候就已经更新了 res[end], arr[i] == 4 时突破长度 // 而 {25,26,27,5,4,3,2,1 } 就不会,因为 1 开始一直往 index[0] 更新,不会影响到整体长度 res[index] = arr[i]; } } return end + 1; } public int binarySearch(int[] arr, int end,int target) { int left = 0; int right = end; while(left < right) { int mid = (right + left) / 2; if(arr[mid] >= target) right = mid; else left = mid + 1; } return left; }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { // 时间复杂度O(N^2),空间复杂度O(N) if (arr.empty()) return 0; int res = 1; vector<int> dp(arr.size(), 1); for (int i = 1; i < arr.size(); ++i) { for (int j = 0; j < i; ++j) { if (arr[i] > arr[j]) { dp[i] = max(dp[i], dp[j] + 1); res = max(res, dp[i]); } } } return res; } };
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # 给定数组的最长严格上升子序列的长度。 # @param arr int整型一维数组 给定的数组 # @return int整型 # class Solution: def p(self, arr): if len(arr) == 0: return 0 dp = [1] * (len(arr)) dp[0] = 1 for i in range(1, len(arr)): for j in range(0, i): if arr[i] > arr[j]: dp[i] = max(dp[i], dp[j]+1) return max(dp) def LIS(self , arr: List[int]) -> int: # write code here return self.p(arr)
介绍一种复杂度的做法,利用到耐心排序算法。具体代码实现与讲解可参考链接。
import java.util.*; public class Solution { public int LIS (int[] arr) { int n = arr.length; if (n == 0) return 0; int[] buckets = new int[n]; int bucketSize = 0; for (int num : arr) { int index = BinarySearch(buckets, 0, bucketSize, num); if (index == bucketSize) bucketSize += 1; buckets[index] = num; } return bucketSize; } private int BinarySearch(int[] arr, int left, int right, int num) { while (left < right) { int mid = left + (right - left) / 2; if (arr[mid] < num) { left = mid + 1; } else { right = mid; } } return left; } }
考虑到本题的本意是考察动态规划,然而给定的时间复杂度是O(n^2),无论暴力还是未优化的动态规划都能通过,失去了题目的本意。。
但是动态规划的做法是可以优化的,使用dp数组记长度为i的上升子序列的末项为dp[i],这使得dp数组拥有有序性,因此可以使用二分查找降低复杂度
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& a) { // write code here int n = a.size(), len = 0; vector<int> dp(n + 1, -2147483648); for(int i = 0; i < n; i++) { if(a[i] == dp[len]) continue; if(a[i] > dp[len]) { len++; dp[len] = a[i]; } else { int b = lower_bound(dp.begin(), dp.begin() + len + 1, a[i]) - dp.begin(); // b不可能等于len或len + 1 dp[b] = min(dp[b], a[i]); } } return len; } };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型vector 给定的数组 * @return int整型 */ int LIS(vector<int>& arr) { // write code here int n=arr.size(); if(n==1) return 1; int res=0; // dp[i]表示以i结尾的最大上升子序列的长度 vector<int>dp(n,1); for(int i=1;i<n;i++){ for(int j=0;j<i;j++){ if(arr[i]>arr[j] ){ dp[i]=max(dp[j]+1,dp[i]); res=max(res,dp[i]); } } } return res; } };
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { int n = arr.length; if (n == 0) { return 0; } int[] dp = new int[n + 1]; int res = 1; for (int i = 1; i <= n; i++) { dp[i] = 1; for (int j = i - 1; j > 0; j--) { if (arr[i - 1] > arr[j - 1]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } }
public int LIS (int[] arr) { // write code here int[] tails=new int[arr.length];// 用于存储当前递增子序列的最小可能尾部元素 int ans=0; for(int num:arr){ int l=0,r=ans;// 在tails数组中查找插入位置,包括加到最后空的一位 while(l<r){ int mid=(l+r)/2; if(tails[mid]>=num) r=mid;// else l=mid+1; } tails[l]=num; if(ans==l) ans++; } return ans; }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * 给定数组的最长严格上升子序列的长度。 * @param arr int整型一维数组 给定的数组 * @return int整型 */ public int LIS (int[] arr) { // if(arr.length==0)return 0; int[] dp=new int[arr.length]; int res=0; for(int i=0;i<arr.length;i++){ if(i==0)dp[i]=1; else{ int max=0; for(int j=0;j<i;j++){ if(arr[j]<arr[i]){ if(dp[j]>max){ max=dp[j]; } } } dp[i]=max+1; } if(dp[i]>res)res=dp[i]; } return res; } }
#include <memory> #include <vector> class Solution { public: int LIS(vector<int>& arr) { vector<int>d(arr.size(),1); int ans=0; if(arr.size()==1||arr.size()==0){ return arr.size(); } for(int i=1;i<arr.size();i++){ for(int j=0;j<i;j++){ if(arr[i]>arr[j]&&d[i]<d[j]+1){ d[i]=d[j]+1; } ans=max(ans,d[i]); } } return ans; } };