This code finds the length of the longest subsequence in n.logn time but not the correct sequence.
How to find the sequence that is longest in n.logn not the length?
#include<bits/stdc++.h>
#include <vector>
int longestIncreasingSubsequence(int arr[], int n) {
std::vector<int> temp;
temp.push_back(arr[0]);
for (int i = 1; i < n; i++) {
if (arr[i] > temp.back()) {
temp.push_back(arr[i]);
} else {
int ind = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
temp[ind] = arr[i];
}
}
return temp.size();
}
int main() {
// Example usage
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = sizeof(arr) / sizeof(arr[0]);
int sequenceSize = longestIncreasingSubsequence(arr, n);
std::cout << "Size of in the Longest Increasing Subsequence: " << sequenceSize;
return 0;
}
Longest subsequence numbers
You need to add two more informations:
The index that corresponds with a value in temp, i.e. where its value came from in the input arr. We can maintain an array idx such that if temp[j] is arr[i], then idx[j] is i.
Given such an index in arr, maintain what its predecessor was at the moment that value was added/updated in temp. We could call that array prev.
When you have that, you can reconstruct the values from the sequence. See also the pseudo code presented at Wikipedia - Longest increasing subsequence.
Here is your code extended with those arrays (I opted for vectors), and the loop to reconstruct the sequence itself:
std::vector<int> longestIncreasingSubsequence2(int arr[], int n) {
std::vector<int> temp;
if (n == 0) return temp;
// backreferences from index in arr to a previous index in arr
std::vector<int> prev(n, 0);
// index from where the corresponding value in temp was retrieved
std::vector<int> idx(n, 0);
temp.push_back(arr[0]);
for (int i = 1; i < n; i++) {
int ind;
if (arr[i] > temp.back()) {
ind = temp.size();
temp.push_back(arr[i]);
} else {
ind = std::lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
temp[ind] = arr[i];
}
idx[ind] = i;
if (ind) prev[i] = idx[ind - 1];
}
// Reconstruct the longest increasing sequence
int k = idx[temp.size() - 1];
for (int j = temp.size() - 1; j >= 0; j--) {
temp[j] = arr[k];
k = prev[k];
}
return temp;
}