How to print Longest Increasing Subsequence(LIS) from a given array?

Question

I can print the length of a LIS by a normal function and Recursive function. But I want to print that index of LIS subsequence in a given array in C++.

Here is my function to find the length of LIS :

int lis( int *arr, int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc ( sizeof( int ) * n );
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];
   /* Free memory to avoid memory leak */
   free( lis );
   return max;
}

here array[10]={7 6 2 3 4 1 8 5 9 10}

here LIS Length=6

I wanna print the index of numbers {2 3 4 6 8 9} ( its not the sequence its the arrray index , what i wanna print ) index of sequence in the array[10]

Answer 1

If anyone interested in Java version. Commented for the explanation.

   public int lengthOfLIS(int[] nums) {
    if(nums.length == 0) return 0;
    // array to store sub-problem solution. L[i] stores the length
    // of the longest increasing sub-sequence ends with nums[i]
    int[] L = new int[nums.length];
    // used to print the actual LIS
    int[] P = new int[nums.length];

    // longest increasing sub-sequence having just one element has length 1
    Arrays.fill(L, 1);
    Arrays.fill(P, -1);

    // start from second element in the array
    for(int i=1; i<nums.length; i++) {

        // do for each element in sub-array nums[0..i-1]
        for(int j=0; j<i; j++) {
            // find longest increasing sub-sequence that ends with nums[j]
            // where nums[j] is less than the current element nums[i]
            // and it extends the original sub-sequence increasingly
            if(nums[j] < nums[i] && L[i] < L[j]+1) {
                L[i] = L[j] + 1;
                // store what index helped to extend L[i] 
                P[i] = j;
            }
        }
    }
     /* find the maximum LIS from L calculated also its index */
    int max=L[0], maxIndex=0;
    for(int i=1; i<nums.length; i++) {
        if(max<L[i]) {
            max=L[i];
            maxIndex=i;
        }
    }
    //starting from index of max-length LIS traverse back 
    //using P array populated earlier
    while (maxIndex >= 0) {
        System.out.print(nums[maxIndex]+", ");
        maxIndex = P[maxIndex];
    }
    return max;
}

Answer 2

void solution() {
  int n;
  cin >> n;
  vector<int> v(n);
  for (int &x : v) cin >> x;
  vector<int> dp(n, 1);
  int i = 0, j = 1;
  vector<int> par(n);
  for (int i = 0; i < n; i++) {
     par[i] = i;
  }
  for (int j = 1; j < n; j++) {
     for (int i = 0; i < j; i++) {
        if (v[j] > v[i] && dp[j] < dp[i] + 1) {
           dp[j] = dp[i] + 1;
           par[j] = i;
        }
     }
  }
  int mx = 1, idx = 0;
  for (int i = 0; i < n; i++) {
     if (dp[i] > mx) {
        mx = dp[i];
        idx = i;
     }
  }
  cout << mx << "\n";
  vector<int> seq;
  while (true) {
     seq.pb(v[idx]);
     if (par[idx] == idx) break;
     idx = par[idx];
  }
  reverse(seq.begin(), seq.end());
  for (int i = 0; i < mx; i++) {
     cout << seq[i] << " ";
  }
}

---

Maintain a parent array and go backwards from the index where the LIS ends parent by parent till you reach the index where parent[index] = index.

Answer 3

Not the best way but you can try it...

int lis(int ar[], int n) {

int max = INT_MIN;
int* lis = new int[n];
int* sub_arr = new int[n];

for (int i = 0; i < n; ++i)
    lis[i] = 1;

for (int i = 1; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
        if(ar[i] > ar[j] && lis[j] + 1 >= lis[i]) {
            lis[i] = lis[j] + 1;
            sub_arr[i] = j;
        }
    }
}

for (int i = 0; i < n; ++i) {
    if(max < lis[i])
        max = ar[i];
}

int k = 0;
stack <int> st;
for (int i = 0; i < n; ++i) {
    if(max == lis[i])
        k = i;
}

cout << "Longest Incresing Subsequence : ";

st.push(k);
while(k > 0) {
    st.push(sub_arr[k]);
    k = sub_arr[k];
}

while (!st.empty()) {
    cout << ar[st.top()] << ' ';
    st.pop();
}
cout << endl;

return max;
}

Answer 4

A dynamic array can be declared with its length equal to maximum length of the increasing sequence. The array ANS will keep the longest increasing sequence.

int *ans=(int*)malloc(sizeof(int)*max);

A temporary variable is used to keep the index of the maximum length in the array.

    int index;
    int length; //used to fill array ANS in reverse order.
    for ( i = 0; i < n; i++ )
      {
          if ( max < lis[i] )
          {
              max = lis[i];
              index=i;
          }
      }
    length=max;
    ans[length-1]=arr[index];  //filling array from the last
                               //last element will be the greatest element
    length--;
    while(index>0)
    {
        for(i=index-1;i>=0;i--)
        {
            if(lis[i]+1==lis[index] && arr[i]<arr[index])
            {
                ans[length-1]=arr[i]; 
                index=i;
                length--;
                break;
            }
        }
    }
    for(i=0;i<max;i++)
    {
        printf("%d",ans[i]);
    }

Here the complexity is O(n) and not O(n2) even though it may be using two loops as we are changing value of index to i whenever if block is entered.

Answer 5

int lis( int *arr, int n )
{
   int *lis, i, j, max = 0, max_index = 0;
   int *print = (int*)malloc(sizeof(int)*n);
   lis = (int*) malloc ( sizeof( int ) * n );
   for ( i = 0; i < n; i++ ){
      lis[i] = 1;
        print[i] = -1
    }
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1){
            lis[i] = lis[j] + 1;
            print[i] = j;
        }
   for ( i = 0; i < n; i++ ){
      if ( max < lis[i] ){
         max = lis[i];
        max_index = i;
      }
    }
    while(max_index >=0){
        printf("%d ",lis[max_inc_index]);
        max_index = print[max_index];
    }
   /* Free memory to avoid memory leak */
   free( lis );

   return max;
}

Use an additional array that keeps track of indices, that are part of the longest subsequence and then traverse the array to print all the corresponding elements.

Answer 6

To print in order you can use recursive approach: calling : printLIS(lis, lis.length -1, arr, max)

public static void printLIS(int[] lis, int lisIndex, int[] arr, int max) {
    if(max == 0) {
        return;
    }
    if(lis[lisIndex] == max) {
        printLis(lis,lisIndex-1, arr, max-1);
        System.out.print(arr[lisIndex] + " ");
    } else {
        printLis(lis,lisIndex-1, arr, max);
    }

}

Answer 7

After calculating lis for each index, take a tmp value equal to max, go backwards on lis array, and every time you find an element equal to max, add that index to the answer and decrement tmp. Hereby you'll get the indexes array in reversed order.

Example code:

int tmp = max;
std::vector<int> indexes;
for( i = n - 1; i >= 0; --i )
   if( lis[ i ] == tmp )
   {
      indexes.push_back( i );
      --tmp;
   }
std::reverse( indexes.begin(), indexes.end());