Longest Increasing Subsequence (LIS) - Slow O(n^2)
A subsequence is obtained by deleting any number of elements while keeping the order of the remaining elements. The chosen elements do not need to be next to each other.
For example, is a subsequence of , while is not: in the original array, appears after .
In the longest increasing subsequence problem, or LIS, we want to choose as many elements as possible so that every next chosen value is strictly larger than the previous one.
You are given an array . Find the maximum length for which there are indices
satisfying
We will also restore one such subsequence.
For , two longest increasing subsequences are and . Both have length .
The most direct solution generates every subsequence. Each element may be taken or skipped, so there are possibilities. This works only for very small .
A greedy choice is tempting, but unreliable. Consider . If we take immediately after , we get stuck with a subsequence of length . The better answer is .
The problem is that an element can be useful or harmful depending on what comes later. Dynamic programming lets every position look back and choose its own best predecessor.
Let be the maximum length of an increasing subsequence whose last chosen element is exactly .
The phrase “ends exactly at ” is the key. Once we require to be last, the previous chosen element may be any such that and .
Every single element is already an increasing subsequence, so the base value is
For every valid predecessor , we may append to a subsequence ending at . Therefore, we try the transition
The LIS may end at any position, so the final answer is
It is not necessarily .
To restore a subsequence, we also store : the predecessor used when the best value of was obtained. If no predecessor is used,
We process the array from left to right. When calculating the state for position , every earlier state is already known.
For each , start with a subsequence containing only . Then inspect every earlier position . If and extending the subsequence from improves the answer, update both and .
Algorithm:
There are states, and each state checks at most earlier positions. This reduces the exponential search to time.
1. Set answer = 0 and last = 0.
2. For every position i from 1 to n:
2.1. Set dp[i] = 1 and parent[i] = 0.
2.2. For every position j from 1 to i - 1:
2.2.1. If a[j] < a[i] and dp[j] + 1 > dp[i]:
- Set dp[i] = dp[j] + 1.
- Set parent[i] = j.
2.3. If dp[i] > answer:
- Set answer = dp[i].
- Set last = i.
3. Create an empty sequence lis.
4. While last != 0:
4.1. Add a[last] to lis.
4.2. Set last = parent[last].
5. Reverse lis.
6. Output answer and lis.
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n;
int a[N];
int dp[N];
int parent[N];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int answer = 0;
int last = 0;
for (int i = 1; i <= n; i++) {
dp[i] = 1;
parent[i] = 0;
for (int j = 1; j < i; j++) {
if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
parent[i] = j;
}
}
if (dp[i] > answer) {
answer = dp[i];
last = i;
}
}
vector<int> lis;
while (last != 0) {
lis.push_back(a[last]);
last = parent[last];
}
reverse(lis.begin(), lis.end());
cout << answer << endl;
for (int x : lis) {
cout << x << ' ';
}
cout << endl;
return 0;
}