DP assume the indices of the array are from 0 to N - 1. So let's define DP[i] to be the length of the LIS (Longest increasing subsequence) which is ending at element with index i. To compute DP[i] we look at all indices j < i and check both if DP[j] + 1 > DP[i] and array[j] < array[i] (we want it to be increasing). If this is true we can update the current optimum for DP[i]. To find the global optimum for the array you can take the maximum value from DP[0...N - 1]
int maxLength = 1, bestEnd = 0; DP[0] = 1; prev[0] = -1; for (int i = 1; i < N; i++) { DP[i] = 1; prev[i] = -1; for (int j = i - 1; j >= 0; j--) if (DP[j] + 1 > DP[i] && array[j] < array[i]) { DP[i] = DP[j] + 1; prev[i] = j; } if (DP[i] > maxLength) { bestEnd = i; maxLength = DP[i]; } }
use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.
another way Longest Increasing Subsequence Size (N log N)
The strategy determined by the following conditions,
1. If A[i] is smallest among all end candidates of active lists, we will start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, we will clone the largest active list, and extend it by A[i].
3. If A[i] is in between, we will find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. We will discard all other lists of same length as that of this modified list.
we can maintain one arrays like this, which always record the smallest elements, the specific process is as follows
Let‘s take a example ， array A {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.A[0] = 0. Case 1. There are no active lists, create one.0.-----------------------------------------------------------------------------A[1] = 8. Case 2. Clone and extend.0.
0, 8. ----------------------------------------------------------------------------- A[2] = 4. Case 3. Clone, extend and discard. 0, 4. 0, 8. Discarded ----------------------------------------------------------------------------- A[3] = 12. Case 2. Clone and extend. 0, 4. 0, 4, 12. ----------------------------------------------------------------------------- A[4] = 2. Case 3. Clone, extend and discard. 0. 0, 4. Discarded. 0, 2, 12. ----------------------------------------------------------------------------- A[5] = 10. Case 3. Clone, extend and discard.
0, 4, 12. Discarded.
0, 2, 10. ----------------------------------------------------------------------------- A[6] = 6. Case 3. Clone, extend and discard.
0, 2, 10. Discarded.
0, 2, 6. ----------------------------------------------------------------------------- A[7] = 14. Case 2. Clone and extend. 0, 2, 6. 0, 2, 6, 14. ----------------------------------------------------------------------------- A[8] = 1. Case 3. Clone, extend and discard.
0, 2. Discarded.
0, 1, 6, 14. ----------------------------------------------------------------------------- A[9] = 9. Case 3. Clone, extend and discard.
0, 2, 6, 14. Discarded.
0, 2, 6, 9. ----------------------------------------------------------------------------- A[10] = 5. Case 3. Clone, extend and discard.
0, 2, 6. Discarded.
0, 2, 6, 9. ----------------------------------------------------------------------------- A[11] = 13. Case 2. Clone and extend. 0, 2, 6, 9. 0, 2, 6, 9, 13. ----------------------------------------------------------------------------- A[12] = 3. Case 3. Clone, extend and discard.
0, 2, 6, 9, 13.
0, 2, 3, 9, 13. ----------------------------------------------------------------------------- A[13] = 11. Case 3. Clone, extend and discard.
0, 2, 6, 9, 13. Discarded.
0, 2, 6, 9, 11. ----------------------------------------------------------------------------- A[14] = 7. Case 3. Clone, extend and discard.
0, 2, 6, 9, 11.
0, 2, 6, 7, 11. ---------------------------------------------------------------------------- A[15] = 15. Case 2. Clone and extend. 0, 2, 6, 9, 11. 0, 2, 6, 9, 11, 15. <-- LIS List ----------------------------------------------------------------------------
Here is a proverb, “Tell me and I will forget. Show me and I will remember. Involve me and I will understand.”
So, pick a suit from deck of cards. Find the longest increasing sub-sequence of cards from the shuffled suit. You will never forget the approach.
#include<bits/stdc++.h> using namespace std;
int LongestIncreasingSubsequenceLength(std::vector<int>& v) { if (v.size() == 0) return 0; std::vector<int> tail; // always points empty slot in tail tail.push_back(v[0]); int n = v.size(); for (int i = 1; i < n; i++) { // Do binary search for the element in, the range from begin to begin + length auto it = lower_bound(tail.begin(), tail.end(), v[i]); // If not present change the tail element to v[i] if (it == tail.begin() + tail.size()) tail.push_back(v[i]);// v[i] is lagger than tail.end() else *it = v[i]; } return tail.size(); }
int main() { int t; scanf("%d", &t); //t = 1; while(t--){ int n; scanf("%d", &n); std::vector<int> v(n+1); for(int i = 0; i < n; i++) scanf("%d", &v[i]); //std::cout << v.size() << " = v.size() "; printf("Length of Longest Increasing Subsequence is %d ", LongestIncreasingSubsequenceLength(v)); } return 0; }
0, 2, 10. Discarded.