Longest Ascending Subsequence (LIS)
1. Definition of LIS
LIS refers to the Longest Increasing Subsequence. I’ll give you the idea of an ascending sequence, if a sequence has the following properties
(x_1, x_2,...,x_n)，x_1 < x_2 < ... < x_n
Copy the codeThen the sequence is said to be ascending. So the LIS class problem is given a sequence (not necessarily a complete ascending order)
(a_1, a_2,... ,a_n)Copy the codeFind the contents of the longest ascending/increasing subsequence in the sequence.
Here is a brief introduction to the basic concepts of substrings and subsequences:
-
Substring: A substring is a sequence of consecutive characters in a string. For example, string = “12345”, then “12”, “234”, and “45” are all substrings. For Java, String.substring () provides methods for subString interception.
-
Subsequence: A string subsequence is a sequence of several characters in the string in the same order. For example, string = “12345”, then “12”, “135”, and “45” are all subsequences. Note that the collection of subsequences of a string must cover the collection of substrings of that string.
With this introduction, the definition of the longest ascending subsequence is easy to understand. Here we give an example: {1,3,5,2,4,6,7,8} to find the length of the longest ascending subsequence of the sequence. We soon see that {1,3,5,6,7,8} is the longest ascending subsequence of the sequence, with length 6. Which brings us to the first kind of question for today.
2. Length solution of LIS
This is an original problem from LeetCode, Leetcode.300, so let’s copy the problem.
Given an unordered array of integers, find the length of the longest ascending subsequence. Example:
Input: [10,9,2,5,3,7,101,18] output: 4 explanation: the longest ascending subsequence is [2,3,7,101], which has a length of 4.Copy the codeHere we mainly introduce two algorithms in detail. There is actually a tree array/segment tree algorithm, but tree array/segment tree is a competition-level method, so I won’t cover it here.
2.1 Dynamic Planning
Basic idea of dynamic programming
The basic idea of dynamic programming is similar to divide-and-conquer, which is to decompose the problem to be solved into several sub-problems and solve the sub-problems in sequence. Different from the divide-and-conquer method, the subproblems of dynamic programming are not independent of each other, that is, there are overlapping subproblems. Since most of the problems solved by dynamic programming have the characteristics of overlapping subproblems, in order to reduce the repeated calculation, each subproblem is solved only once, and then the different states of different stages are saved in a dynamic programming table.
Dynamic programming solves three problems
Dynamic planning topic in OJ problem accounted for a large proportion, this kind of topic brush much, I also summarized some One Rule To Rule Them All rules, such as the following three elements of dynamic planning, master this routine, this kind of topic can be handy.
- Define the dynamic programming solution object: simply define what the dp[I] problem or transition state is. In general, the problem is well defined and more than half successful.
- State transfer equation: state transfer is based on the sub-problem (the previous stage) state and decision to derive the state of this problem (the current stage), determine the decision method, can write state transfer equation.
- Boundary conditions: The state transition equation is a recursion that requires a triggered boundary condition to finally solve the dynamic programming problem.
LIS length
By analyzing the longest ascending subsequence, it is found that we do not know the beginning element of LIS, nor the end element of LIS, nor the number of elements contained in LIS. In this case, it is difficult for us to analyze the problem quantitatively. So, we fix one thing, the ending element of LIS. For example, we know that the ending element of LIS is nums[I], and we can easily find that LIS ending with nums[I] is an LIS with I characters before NUMS. so
- Define dynamic programming solving problem: dp[I] means to determine the length of LIS terminated by nums[0] ~ NUMs [I] substring ending with the ith character in numS array. The LIS of nums[0] ~ nums[len-1] must be the largest in dp[0] ~ dp[len-1].
With the dynamic programming problem defined, the next step we need to look for is the transition equation. If we take dp[I] as an example, how can we find LIS ending with nums[I]? Since dp[I] represents a LIS that is determined to end with NUMs [I], nums[I] can be determined to be in this subsequence. So, where do we get the rest of the elements? The relation between the previous state (dp[j], j < I) described by the state transition equation and the current state (DP [I]), it is natural for us to think of calculating DP [I] by dp[j] (j < I). So, which dp[j] or which dp[j] is derived? Naturally, we find that it is derived from the largest dp[j] and the corresponding NUMs [j] of this dp[j] needs to be less than dp[I], otherwise it does not satisfy the rising property, so
- Dp [I] = Max(DP [J] + 1), 0 <= j < I < Len and NUMs [I] > NUMs [J]
- Boundary conditions: this is nicely given, dp[0] = 1, representing the length of LIS ending with the first element nums[0].
A Demo
Let’s take {1,3,5,2,4,6,7} as an example to simulate the process:
Obviously, the length of LIS = DP [6] = 5
Show me the Code – Dynamic programming code
public int lengthOfLIS(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int max = 1;
int[] dp = new int[len];
Arrays.fill(dp, 1);
for (int i = 0; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
}
}
max = Math.max(dp[i], max);
}
return max;
}
Copy the codeComplexity analysis
Time complexity: O(n^2), I traversed from 0 to n-1, j traversed from 0 to i-1, and the innermost layer of logic was calculated
0 + 1 + 2 + 3 +... + n - 2Copy the codeSo it’s order n^2.
However, our LeetCode submission found that?? Obviously, this O(n^2) time complexity algorithm is not optimal.
2.2 Greed + 2
Greedy + dichotomous solution
In terms of time complexity, how can we reduce O(n^2) time complexity even lower? First of all, it’s clear that a traversal is inevitable, so can the remaining n be reduced even further? And the answer is you can reduce it to log n. We have this naive greedy idea that if I maintain a subsequence that rises more slowly, is it easier to add more elements? For example, given an original sequence {1,3,5,2,4,6,7,8}, the subsequence {1,2} rises more slowly than {1,3}. In both cases, we choose {1,2} to ensure that there is more space to rise later. So how do we find a sequence that rises slowest? We maintain a list named slow, representing the slowest ascending sequence in NUMs [], traversing NUMs, for a nums[I], if:
-
The last element of nums[I] > slow (that is, greater than all elements in slow) is added to the end of slow
-
The last element of nums[I] <= slow, we look for the first number in the slow list that is greater than or equal to nums[I] and replace it. Since the sequence is not strictly monotonically increasing, we can easily find this number using dichotomy. This step is down to log(n).
-
The length of the resulting slow array is equal to the length of LIS
A Demo
Let’s take an example of {1,3,5,2,4,6,7,0} to simulate this process:
- Initial slow = []
- Nums [0] = 1, so slow = [1]
- Nums [1] = 3, so slow = [1, 3]
- Nums [2] = 5, so slow = [1, 3, 5]
- Nums [3] = 2, 2 replaces 3, so slow = [1, 2, 5]
- Nums [4] = 4, 4 replaces 5, so slow = [1, 2, 4]
- Nums [5] = 6, so slow = [1, 2, 4, 6]
- Nums [6] = 7, so slow = [1, 2, 4, 6, 7]
- Nums [7] = 0, 0 replaces 1, so slow = [0, 2, 4, 6, 7]
- The length of LIS is equal to the length of slow is equal to 5
Finally, we find that the length of slow is the length of LIS, but the slow list is obviously not an LIS or even a subsequence. In the step of NUMS [7] = 0, the nature of the sub-sequence is destroyed. Here, the slow list is to record the minimum sequence, representing a “most probable”, which is only a replacement for LIS calculation by this algorithm.
Show me the code – Greedy + binary code
public int lengthOfLIS2(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
LinkedList<Integer> slow = new LinkedList<>();
for (int i = 0; i < len; i++) {
int ele = nums[i];
if (slow.isEmpty() || ele > slow.getLast()) {
slow.add(ele);
} else {
int idx = binarySearchLargerEleIndex(slow, ele);
slow.set(idx, ele);
}
}
return slow.size();
}
private int binarySearchLargerEleIndex(LinkedList<Integer> low, int val) {
int left = 0;
int right = low.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
int ele = low.get(mid);
if (ele < val) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
Copy the codeComplexity analysis
Spatial complexity: O(k), where K is the length of LIS. This is obvious. We have constructed a slow list with a length of K.
2.3 What ‘s the diffence?
It can be found that the greedy + binary algorithm is better than the dynamic programming algorithm in both time complexity and space complexity, so can we say that the former is better than the latter? The answer is not necessarily, the former is obviously better in finding the length of LIS. However, DP algorithm is superior to greedy + dichotomy algorithm in many aspects when calculating the value of specific LIS solution. This brings us to the second class of problems here.
3. Solution of LIS sequence value
Let’s describe the problem. Given an unordered array of integers, find the longest ascending subsequence. Example:
Input:,9,2,5,3,7,101,18 [10] output:,3,7,101 [2] or [2,5,7,101]Copy the codeHere we are no longer asking for the length of LIS, but for a specific LIS sequence. Again, here we try two approaches.
3.1 Dynamic Planning
Their thinking
In the previous analysis of LIS length, we know that LIS may appear in any subsequence ending with NUMs [I], but we do not know where it will appear. In the problem of finding LIS length, we find the maximum in dp[I]. So here, in finding a specific LIS, for each dp[I], we need to use a list res to store a LIS ending at NUMs [I]. In this way, when dp[I] with the maximum value is finally found, the corresponding res[I] is LIS of the whole string.
Show me the Code – Dynamic programming
public List<Integer> getSeqOfLIS(int[] nums) { int len = nums.length; if (len == 0) return new ArrayList<>(); Int dp[] = new int[len]; // dp[I] = new int[len]; Arrays.fill(dp, 1); List<List<Integer>> res = new ArrayList<>(); res = new ArrayList<>(); int maxId = -1; int maxLength = Integer.MIN_VALUE; for (int i = 0; i < len; i++) { List<Integer> tmp = new ArrayList<>(); Int index = -1; // Int index = -1; // Int index = -1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; index = j; } } if (index > -1) { tmp.addAll(res.get(index)); } tmp.add(nums[i]); res.add(tmp); if (tmp.size() > maxLength) { maxLength = tmp.size(); maxId = i; } } return res.get(maxId); }Copy the codeComplexity analysis
Space complexity: O(n), there are two auxiliary arrays or lists :dp[], res[], the space complexity is 2n, can actually reduce the space complexity to N, interested students can write down the code to reduce the space complexity to N. For details, please refer to Q300_1SeqOfLIS. Time complexity: O(n^2)
3.2 Greed + two
Analysis Idea 1
When I wrote this blog, I referred to many others’ blogs. Some people said that the greedy + dichotomy method may not be able to find a specific LIS solution value, because the nature of sub-sequences may be damaged when maintaining the slowest ascending sequence, slow. So, we really can’t get an LIS? Let’s briefly review the previous simulation process:
The original sequence is {1,3,5,2,4,6,7,0} :
-
Initial slow = []
.
-
Nums [5] = 6, so slow = [1, 2, 4, 6]
-
Nums [6] = 7, so slow = [1, 2, 4, 6, 7]
-
Nums [7] = 0, 0 replaces 1, so slow = [0, 2, 4, 6, 7]
-
The length of LIS is equal to the length of slow is equal to 5
We can see that the properties of the subsequence are broken at the step where NUMs [7] = 0, but in fact for this example we find an LIS at the step where nums[6] = 7. And here it seems that this approach works, right?
- Firstly, the length of LIS is obtained by the method of once greedy + dichotomy.
- Repeat the same process and stop returning the current LIS when the slow array reaches the length of LIS. Just like the above example, we seem to find such an LIS [1, 2, 4, 6, 7].
But our naive idea is wrong. A simple counterexample would be to add {1,3,5,2,4,6,7,0,10} to the original sequence.
It is obvious that an LIS is {1, 2, 4, 6, 7,10} and of length 6. However, the slow list we maintain first reaches length 6 with slow = [0, 2, 4, 6, 7,10], which is clearly not an LIS.
Analysis Idea 2
The above method is not feasible, so is there any other method? Note that manipulation of the SLOW list is only possible to destroy the properties of the LIS-property neutron sequence with substitution. That is, the position of slow[I] in the slow table in the original sequence is not necessarily to the left of slow[I +1]. Note that slow[I] and slow[I +1] have a second meaning, indicating that slow[I +1] is preceded by a smaller element, although it may not be numerically slow[I], as slow[I] may have been replaced. So for nums arrays, we can consider maintaining a preValues array that records which values slow[I] can link from the original NUMs [] array. Example: the original sequence is {1,3,5,2,4,6,7,0} :
- Initial slow = []
- Nums [0] = 1, slow = [1], preValues = [null]
- Nums [1] = 3, slow = [1, 3], preValues = [null, 1]
- Nums [2] = 5, slow = [1, 3, 5], preValues = [null, 1, 3]
- Nums [3] = 2, 2 replaces 3, so slow = [1, 2, 5], preValues = [null, 1, 3, 1]
- Nums [4] = 4, 4 replaces 5, so slow = [1, 2, 4], preValues = [null,1, 3, 1, 2]
- Nums [5] = 6, slow = [1, 2, 4, 6], preValues = [null, 1, 3, 1, 2, 4]
- Nums [6] = 7, slow = [1, 2, 4, 6, 7], preValues = [null, 1, 3, 1, 2, 4, 6]
- Nums [7] = 0, 0 replaces 1, so slow = [0, 2, 4, 6, 7], preValues = [NULL, 1, 3, 1, 2, 4, 6, null]
- The length of LIS is equal to the length of slow is equal to 5
- Starting from the last element of the SLOW list, look up the preValue array backtrace, 7 -> 6 -> 4 -> 2 -> 1, and you end up with an LIS.
Show me the code – Greedy + 2
public List<Integer> getSeqOfLIS3(int[] nums) {
int len = nums.length;
if (len == 0) {
return new ArrayList<>();
}
LinkedList<Integer> preValues = new LinkedList<>();
LinkedList<Integer> low = new LinkedList<>();
for (int i = 0; i < len; i++) {
int ele = nums[i];
if (low.isEmpty() || ele > low.getLast()) {
low.add(ele);
if (low.size() == 1) {
preValues.add(null);
} else {
preValues.add(low.get(low.size() - 2)); }}else {
int idx = binarySearchLargerEleIndex(low, ele);
low.set(idx, ele);
if (idx == 0) {
preValues.add(null);
} else {
preValues.add(low.get(idx - 1));
}
}
}
LinkedList<Integer> res = new LinkedList<>();
res.addLast(low.getLast());
Integer pre = low.getLast();
for (int i = nums.length - 1; i >= 0; i--) {
Integer numVal = nums[i];
if(pre.equals(numVal) && preValues.get(i) ! =null) { res.addFirst(preValues.get(i)); pre = preValues.get(i); }}return res;
}
Copy the codeComplexity analysis
Space complexity: O(n) Time complexity: O(nlogn)
3.3 So, what’s the diffence?
In obtaining a specific LIS solution value, the greedy + binary algorithm is also due to the DP algorithm. But further down the line, DP is better in terms of the breadth of solutions than the greedy + binary method, which brings us to the third class of problems.
4. Find all LIS
This is an original problem from LeetCode very similar to Leetcode.673, so let’s copy the problem.
Given an unsorted array of integers, find the number of longest incrementing subsequences. Example 1: Input: [1,3,5,4,7] Output: 2 Explanation: There are two longest increasing subsequences, which are [1,3, 4,7] and [1,3,5, 7]. Example 2: Input: [2,2,2,2,2] Output: 5 Explanation: The longest increasing subsequence is of length 1, and there are five subsequences of length 1, so output 5.Copy the codeThere are many solutions to the number of LIS in LeetCode, such as dynamic programming (O(n^2)), linear segment (O(nlogn)). But here, we’re more concerned with finding all the solutions. Because, for optimization problems in practical application, we don’t care about how many solutions there are in many cases, but how many solutions there are and what the solutions are. So, here we want all of LIS. Incidentally, the number of LIS is naturally obtained after all LIS are calculated.
4.1 Dynamic Planning
For many strings, such as {1,3,5,2,4,6,7}. Obviously, it has more than one LIS, {1,3,5,6,7} and {1,2,4,6,7}. So in the process of solving dynamic programming, how to record all the solutions?
- First, we analyze where multiple LIS may appear. There are two cases:
- In the first case, multiple LIS appear in the subsequence ending with NUMs [I], which can be illustrated by example 1 of LeetCode.673.
- In the second case, multiple LIS may appear in subsequences ending with different NUMs [I]. This is a good example, {3, 5, 1, 2}, two LIS {3, 5} and {1, 2}.
- Then, we need to keep the set of LIS for each substring ending in nums[I], and finally merge the set with length equal to LIS_maxLen according to the length of LIS.
We noticed that in the code of obtaining a LIS sequence value in 3.1 dynamic programming, the condition dp[j] + 1 > dp[I] can ensure that the first LIS in the sequence is obtained, and it is easy to find other LIS in the first case by adding another branch of DP [j] + 1 == DP [I].
for (int i = 0; i < len; i++) { List<Integer> tmp = new ArrayList<>(); Int index = -1; // Int index = -1; // Int index = -1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; index = j; }}}Copy the codeIt should be noted that dp[j] + 1 May increase in some values. Take {1,3,5,2,4,6,7} as an example, dp[j] + 1 increases from 2 to 5 at dp[6]. Then the previous solution needs to be directly replaced when maintaining the local LIS solution.
4.2 Show me the Code – Dynamic Planning
public List<List<Integer>> getAllSeqOfLIS(int[] nums) {
int len = nums.length;
if (len == 0) return new ArrayList<>();
// dp[I] specifies the length of the longest increasing subsequence of nums[0] to nums[I] substrings ending with element I
int[] dp = new int[len];
Arrays.fill(dp, 1);
// The first layer List< I > represents the set of the longest increasing subsequences ending with I elements
// List represents all subsequences
// The third layer List represents a subsequence
List<List<List<Integer>>> allSeqList = new ArrayList<>();
int maxLen = 1;
for (int i = 0; i < len; i++) {
List<List<Integer>> local = new ArrayList<>();
int lastIndex = -1;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
if (dp[j] + 1 > dp[i]) {
// Replace the previous partial LIS result
local.clear();
lastIndex = j;
local.addAll(getNewCopyDoubleList(allSeqList.get(j)));
for (List<Integer> seq : local) {
seq.add(nums[i]);
}
dp[i] = dp[j] + 1;
} else if (dp[j] + 1 == dp[i]) {
List<List<Integer>> more = getNewCopyDoubleList(allSeqList.get(j));
for(List<Integer> seq : more) { seq.add(nums[i]); } local.addAll(more); }}}if (lastIndex == -1) {
List<Integer> oneEleList = new ArrayList<>(Arrays.asList(nums[i]));
local.add(oneEleList);
}
allSeqList.add(getNewCopyDoubleList(local));
maxLen = Math.max(dp[i], maxLen);
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < len; i++) {
if (dp[i] == maxLen) {
res.addAll(newArrayList<>(allSeqList.get(i))); }}return res;
}
private List<List<Integer>> getNewCopyDoubleList(List<List<Integer>> doubleList) {
List<List<Integer>> result = new ArrayList<>();
for (List<Integer> list : doubleList) {
result.add(new ArrayList<>(list));
}
return result;
}
Copy the code4.3 Complexity Analysis
Space complexity: O(n^2)
Time complexity: O(n^2)
conclusion
So far, we have used dynamic programming to solve a class of LIS problems, finding the length of LIS, finding a LIS, finding the number of LIS and finding all LIS. Although the dynamic programming approach is not the best in terms of time complexity for some problems, it does have the widest applicability. Dynamic programming is also a very common type in general OJ questions (interview questions or written questions). Here, the practice of dynamic programming is deeply analyzed from the four sub-problems of LIS, hoping to be helpful to readers. If you think it’s good, please give a thumbs-up and support it
The resources
- Cloud.tencent.com/developer/a…
- Blog.csdn.net/lxt_Lucia/a…