A chain of integers is simply a list of integers in strictly increasing order. F

Question

A chain of integers is simply a list of integers in strictly increasing order. For example, 1, 5, 7, 8, 11, 14 is a chain.

Consider the following problem. You are given a list of n distinct integers a[0], a[1], ..., a[n-1]. Your job is to delete some integers in this list so the remaining integers (with their original relative ordering) forms a chain. This should be done with the fewest possible deletions.

For example, if the list is [5, 2, 9, 6, 4, 7, 1, 8] then we can delete 5, 9, 6, 4, 1 which leaves the chain 2, 6, 7, 8. Another possible chain of length 4 we can obtain is 2, 4, 7, 8. There is no way to delete some integers to leave a chain of length 5.

Briefly describe an O(n2) algorithm for finding the longest chain in a list of integers by reducing it to the longest common subsequence problem. Note, the LCS algorithm we saw in class works for lists of integers as well as strings.

Does this reduction mean every algorithm for solving the integer chain problem takes ?(n2) time?

Explanation / Answer

Commonly known as LIS ,

/* A Naive recursive implementation of LIS problem */
#include<stdio.h>
#include<stdlib.h>

/* To make use of recursive calls, this function must return two things:
   1) Length of LIS ending with element arr[n-1]. We use max_ending_here
      for this purpose
   2) Overall maximum as the LIS may end with an element before arr[n-1]
      max_ref is used this purpose.
The value of LIS of full array of size n is stored in *max_ref which is our final result
*/
int _lis( int arr[], int n, int *max_ref)
{
    /* Base case */
    if(n == 1)
        return 1;

    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]

    /* Recursively get all LIS ending with arr[0], arr[1] ... ar[n-2]. If
       arr[i-1] is smaller than arr[n-1], and max ending with arr[n-1] needs
       to be updated, then update it */
    for(int i = 1; i < n; i++)
    {
        res = _lis(arr, i, max_ref);
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }

    // Compare max_ending_here with the overall max. And update the
    // overall max if needed
    if (*max_ref < max_ending_here)
       *max_ref = max_ending_here;

    // Return length of LIS ending with arr[n-1]
    return max_ending_here;
}

// The wrapper function for _lis()
int lis(int arr[], int n)
{
    // The max variable holds the result
    int max = 1;

    // The function _lis() stores its result in max
    _lis( arr, n, &max );

    // returns max
    return max;
}

/* Driver program to test above function */
int main()
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d ", lis( arr, n ));
    getchar();
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.