n.Logn algorithm to find longest subsequence not the length

Question

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

Answer 1

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;
}