Find the solution to the longest increasing subsequence in an array
- 2020-04-02 01:02:58
- OfStack
Storage expansion algorithm n2 programming c writes a program with the lowest possible time complexity to find the length of the longest increasing sequence in a one-dimensional array (N elements).
For example, in the sequence 1, -1,2, -3,4, -5,6, -7, its longest increasing subsequence is 1,2,4,6 or -1,2,4,6. (programming beauty p198-202)
Analysis and solution
According to the requirements of the problem, find the longest increasing sequence in the one-dimensional array, that is, find a numbered sequence b[0],b[1],... B [m] (0 < B = [0] < B [1] < ... < B [m] < N), so that array[b[0]] < Array [1] [b] < ... < Array [b] [m].
Method a
According to the definition of non-sequentiality, we know that after the stages are arranged in a certain order, for a given stage state, the states of its previous stages cannot directly affect its future decisions, but can only indirectly affect its current state. In other words, each state is a complete summary of history.
Again, if we take the sequence 1, -1, 2, -3, 4, -5, 6, -7, we don't care what the two values before 4 are after we find 4, because it has no direct effect on finding 6. Therefore, this problem satisfies no aftereffect and can be solved by using dynamic programming.
The target string can be analyzed by the rule of Numbers: 1, -1, 2, -3, 4, -5, 6, -7.
Use I to indicate the current traversal position
When I =1, obviously, the longest increasing sequence is (1), and the sequence length is 1.
When I is equal to 2, that's because of minus 1 < 1. Therefore, the string must be rebuilt after the first value is discarded. The current increasing sequence is (-1) with length 1.
When I =3, because of 2 > 1, 2, > 1. Therefore, the longest increasing sequence is (1,2), (-1,2), and the length is 2. In this case, whether it's a 1 before a 2 or a minus 1 has no direct effect on the sequence of increments that follow. (but in other cases it might)
And so on, we come to the following conclusion.
Suppose that in the first I elements of the target array[], the length of the longest increasing subsequence is LIS[I]. So,
LIS [I + 1) = Max {1, LIS [k] + 1}, Array [I + 1) > Array [k], For any k < = I
That is, if array[I +1] is greater than array[k], then the I +1 element can be connected to the long subsequence of LIS[k] to form a longer subsequence. At the same time, array[I +1] itself can form at least one subsequence of length 1.
According to the above analysis, the code list can be obtained:
C + + code:
The time complexity of this method is O(N2 + N) = O(N2).
Method 2
In the previous analysis, when we looked at the I +1 element, we did not consider the distribution of the I elements. Now let's look at it another way, which is when we look at the I +1 element we look at the I elements.
For any of the preceding I elements, if the largest element of the subsequence is smaller than array[I +1], then array[I +1] can be added to the subsequence to form a new increasing subsequence.
For example, when I =4, the target sequence is 1, -1,2, -3, 4, -5, 6, -7, and the longest increasing sequence is (1,2),(-1,2).
So we only have 4 > 2, you can add 4 directly to the preceding subsequence to form a new increasing subsequence.
Therefore, we want to find an increasing sequence of the first I elements so that the largest element of this increasing sequence is smaller than array[I +1] and as long as possible. After adding array[I +1] to the increasing subsequence, the longest increasing subsequence with array[I +1] as the largest element can be found.
It is still assumed that in the first I elements of an array, the length of the longest increasing subsequence with array[I] as the largest element is LIS[I].
Meanwhile, suppose:
The minimum value of the maximum element of an increasing subsequence of length 1 is MaxV[1].
The minimum value of the maximum element of an increasing subsequence of length 2 is MaxV[2].
...
The minimum value of MaxV[LIS[I]] is the maximum element of the increasing subsequence of LIS[I].
The invariant P of this cycle is:
P: k is the length of the longest increasing subsequence of sequence a[0: I], 0 Or less I < n.
It is easy to see that the value of a[I] plays a key role in the cycle from I -1 to I. If a[I] can extend the length of the longest increasing subsequence of a[0; I -1], then k=k+1, otherwise k remains unchanged. Let the ending element of the longest increasing subsequence of length k in a[0;i-1] be a[j](0 Or less j Or less i-1), then it can be extended when a[I] p a[j], otherwise it cannot be extended. If the sequence a[0; I -1] has multiple longest increasing subsequences of length k, what information should be stored? It is easy to see that as long as the minimum value b[k] of the ending element in the sequence a[0; I -1] is stored, Therefore, the cyclic invariant P needs to be enhanced to:
P: 0 Or less I < n; K is the length of the longest increasing subsequence of sequence a[0; I].
B [k] is the value of the smallest ending element in all incrementing subsequences of length k in sequence a[0; I].
Accordingly, the induction hypothesis is enhanced to the following: the correct algorithm is known to calculate the length k of the longest increasing subsequence of a[0;i-1](I < n) and the minimum ending element value b[k] in all the increasing subsequence of a[0; I] of length k.
After the induction hypothesis is enhanced, in the cycle from I -1 to I, when a[I] p b[k], k=k+1, and b[k]=a[I], otherwise, k value remains unchanged. Note that when a[I] p b[k], the value of k increases, and the value of b[k] is a[I]. So, how should the value of b[l;k] change when a[I] < b[k]? If a [I] < When b[l] Or less a[I] Or less b[k], it is noted that array b is in order, and subscript j can be found by binary search algorithm, so that b[j-1] Or less a[I] Or less b[j]. At this point, the values of b[1;j-1] and b[j+1;k] remain unchanged, and the value of b[j] changes to a[I].
For example, in the sequence 1, -1,2, -3,4, -5,6, -7, its longest increasing subsequence is 1,2,4,6 or -1,2,4,6. (programming beauty p198-202)
Analysis and solution
According to the requirements of the problem, find the longest increasing sequence in the one-dimensional array, that is, find a numbered sequence b[0],b[1],... B [m] (0 < B = [0] < B [1] < ... < B [m] < N), so that array[b[0]] < Array [1] [b] < ... < Array [b] [m].
Method a
According to the definition of non-sequentiality, we know that after the stages are arranged in a certain order, for a given stage state, the states of its previous stages cannot directly affect its future decisions, but can only indirectly affect its current state. In other words, each state is a complete summary of history.
Again, if we take the sequence 1, -1, 2, -3, 4, -5, 6, -7, we don't care what the two values before 4 are after we find 4, because it has no direct effect on finding 6. Therefore, this problem satisfies no aftereffect and can be solved by using dynamic programming.
The target string can be analyzed by the rule of Numbers: 1, -1, 2, -3, 4, -5, 6, -7.
Use I to indicate the current traversal position
When I =1, obviously, the longest increasing sequence is (1), and the sequence length is 1.
When I is equal to 2, that's because of minus 1 < 1. Therefore, the string must be rebuilt after the first value is discarded. The current increasing sequence is (-1) with length 1.
When I =3, because of 2 > 1, 2, > 1. Therefore, the longest increasing sequence is (1,2), (-1,2), and the length is 2. In this case, whether it's a 1 before a 2 or a minus 1 has no direct effect on the sequence of increments that follow. (but in other cases it might)
And so on, we come to the following conclusion.
Suppose that in the first I elements of the target array[], the length of the longest increasing subsequence is LIS[I]. So,
LIS [I + 1) = Max {1, LIS [k] + 1}, Array [I + 1) > Array [k], For any k < = I
That is, if array[I +1] is greater than array[k], then the I +1 element can be connected to the long subsequence of LIS[k] to form a longer subsequence. At the same time, array[I +1] itself can form at least one subsequence of length 1.
According to the above analysis, the code list can be obtained:
C + + code:
int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i < n; i++)
if(max < a[i])
max = a[i];
return max;
}
int LIS(vector<int> &array)
{
int *a = new int[array.size()];
for(int i = 0; i < array.size(); i++)
{
a[i] = 1;//Initializes the default length
for(int j = 0; j < i; j++) //The longest sequence in front
{
if(array [i] > array [j] && a[j] + 1 > a[i]) //The current number is larger than the JTH, and the tag array needs to be updated
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}
The time complexity of this method is O(N2 + N) = O(N2).
Method 2
In the previous analysis, when we looked at the I +1 element, we did not consider the distribution of the I elements. Now let's look at it another way, which is when we look at the I +1 element we look at the I elements.
For any of the preceding I elements, if the largest element of the subsequence is smaller than array[I +1], then array[I +1] can be added to the subsequence to form a new increasing subsequence.
For example, when I =4, the target sequence is 1, -1,2, -3, 4, -5, 6, -7, and the longest increasing sequence is (1,2),(-1,2).
So we only have 4 > 2, you can add 4 directly to the preceding subsequence to form a new increasing subsequence.
Therefore, we want to find an increasing sequence of the first I elements so that the largest element of this increasing sequence is smaller than array[I +1] and as long as possible. After adding array[I +1] to the increasing subsequence, the longest increasing subsequence with array[I +1] as the largest element can be found.
It is still assumed that in the first I elements of an array, the length of the longest increasing subsequence with array[I] as the largest element is LIS[I].
Meanwhile, suppose:
The minimum value of the maximum element of an increasing subsequence of length 1 is MaxV[1].
The minimum value of the maximum element of an increasing subsequence of length 2 is MaxV[2].
...
The minimum value of MaxV[LIS[I]] is the maximum element of the increasing subsequence of LIS[I].
The invariant P of this cycle is:
P: k is the length of the longest increasing subsequence of sequence a[0: I], 0 Or less I < n.
It is easy to see that the value of a[I] plays a key role in the cycle from I -1 to I. If a[I] can extend the length of the longest increasing subsequence of a[0; I -1], then k=k+1, otherwise k remains unchanged. Let the ending element of the longest increasing subsequence of length k in a[0;i-1] be a[j](0 Or less j Or less i-1), then it can be extended when a[I] p a[j], otherwise it cannot be extended. If the sequence a[0; I -1] has multiple longest increasing subsequences of length k, what information should be stored? It is easy to see that as long as the minimum value b[k] of the ending element in the sequence a[0; I -1] is stored, Therefore, the cyclic invariant P needs to be enhanced to:
P: 0 Or less I < n; K is the length of the longest increasing subsequence of sequence a[0; I].
B [k] is the value of the smallest ending element in all incrementing subsequences of length k in sequence a[0; I].
Accordingly, the induction hypothesis is enhanced to the following: the correct algorithm is known to calculate the length k of the longest increasing subsequence of a[0;i-1](I < n) and the minimum ending element value b[k] in all the increasing subsequence of a[0; I] of length k.
After the induction hypothesis is enhanced, in the cycle from I -1 to I, when a[I] p b[k], k=k+1, and b[k]=a[I], otherwise, k value remains unchanged. Note that when a[I] p b[k], the value of k increases, and the value of b[k] is a[I]. So, how should the value of b[l;k] change when a[I] < b[k]? If a [I] < When b[l] Or less a[I] Or less b[k], it is noted that array b is in order, and subscript j can be found by binary search algorithm, so that b[j-1] Or less a[I] Or less b[j]. At this point, the values of b[1;j-1] and b[j+1;k] remain unchanged, and the value of b[j] changes to a[I].
template<typename T> vector<int> find_lis(vector<T> &a)
{
vector<int> b, p(a.size());//B is the subscript of the last element of the store increasing sequence of length k
//For example, b[1] is the index & NBSP; that stores the minimum value of the largest element of the increasing sequence;
//B is the index that stores the oldest sequence
int u, v;
if (a.size() < 1)
return b;
b.push_back(0);
for (int i = 1; i < (int)a.size(); i++)
{
if (a[b.back()] < a[i])
{
p[i] = b.back();
b.push_back(i);
continue;
}
for (u = 0, v = b.size()-1; u < v;) //Binary search
{
int c = (u + v) / 2;
if (a[b[c]] < a[i])
u=c+1;
else v=c;
}
if (a[i] < a[b[u]])
{
if (u > 0)
p[i] = b[u-1];
b[u] = i;
}
}
for (u = b.size(), v = b.back(); u--; v = p[v])
b[u] = v;
return b;
}