Print Longest Increasing Subsequence

Practice Link

Given an integer n and an array of integers arr, return the Longest Increasing Subsequence which is Index-wise lexicographically smallest. Note - A subsequence S1 is Index-wise lexicographically smaller than a subsequence S2 if in the first position where S1 and S2 differ, subsequence S1 has an element that appears earlier in the array arr than the corresponding element in S2. LIS of a given sequence is defined as that longest possible subsequence all of whose elements are in increasing order. For example, the length of LIS for 80 is 6 and the LIS is 80.

DP Approach#

Intuition:

• For every element find the LIS ending with this element.
• For each element:
  • Check all elements smaller than it.
  • Take max of existing lis and lis of smaller element + 1 → max(lis[i], lis[j]+1).
• To reconstruct the actual LIS (not just its length), maintain a hash array where hash[i] stores the index of the predecessor of element i in the best LIS ending at i. When a better LIS through j is found for element i, set hash[i] = j. Starting from the index of the maximum LIS value and following hash links backwards traces the full subsequence, which is then reversed.
• Initializing hash[i] = i (self-loop) acts as the sentinel to stop the backtracking when we reach the first element of the LIS.

void printLis(vector<int> &arr, vector<int> &hash, int idx, vector<int>& result)
    {
        result.push_back(arr[idx]);
        while(hash[idx] != idx)
        {
            idx = hash[idx];
            result.push_back(arr[idx]);
        }
        reverse(result.begin(), result.end());
    }
  
    vector<int> longestIncreasingSubsequence(int n, vector<int>& arr) {
        vector<int> lis(n);
        vector<int> hash(n);
        lis[0] = 1;
        
        for(int i=1;i<n;i++)
        {
            hash[i] = i;
            lis[i] = 1;
            for(int j=0;j<i;j++)
            {
                if(arr[i] > arr[j] && lis[i] < 1 + lis[j])
                {
                    lis[i]  = 1+lis[j];
                    hash[i] = j;
                }
            }
        }
        
        int lisIdx = max_element(lis.begin(), lis.end()) - lis.begin();
        
        vector<int> result;
        printLis(arr, hash, lisIdx, result);
        
        return result;
    }

Time Complexity: O(n*n)

Space Compelexity: O(n)