Question

Suppose you are given an array of n integers a1, a2, ..., an. You need to find out the length of its longest sub-array (not necessarily contiguous) such that all elements in the sub-array are sorted in non-decreasing order. For example, the length of longest sub-array for {5, 10, 9, 13, 12, 25, 19, 70} is 6 and one such sub-array is {5, 10, 13, 19, 70}. Note you may have multiple solutions for this case. Use dynamic programming to solve this problem. Answer the following questions.

a) What is the optimal substructure of this problem?

b) Show the pseudo code of your solution and its complexity in terms of asymptotic analysis.

c) Use two examples to demonstrate how your approach works. In cases where there are multiple longest sub-arrays, you just need to show one of them.

d) How can we use the table generated by the dynamic programming algorithm to tell whether there is more than one optimal solution?

Answer 1

Optimal Substructure:
Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
Then, L(i) can be recursively written as:
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.
To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Thus, we see the LIS problem satisfies the optimal substructure property as the main problem can be solved using solutions to subproblems.

// Utility function to print LIS

void printLIS(vector<int>& arr)

{

    for (int x : arr)

        cout << x << " ";

    cout << endl;

}

// Function to construct and print Longest Increasing

// Subsequence

void constructPrintLIS(int arr[], int n)

{

    // L[i] - The longest increasing sub-sequence

    // ends with arr[i]

    vector<vector<int> > L(n);

    // L[0] is equal to arr[0]

    L[0].push_back(arr[0]);

    // start from index 1

    for (int i = 1; i < n; i++)

    {

        // do for every j less than i

        for (int j = 0; j < i; j++)

        {

            /* L[i] = {Max(L[j])} + arr[i]

            where j < i and arr[j] < arr[i] */

            if ((arr[i] > arr[j]) &&

                    (L[i].size() < L[j].size() + 1))

                L[i] = L[j];

        }

        // L[i] ends with arr[i]

        L[i].push_back(arr[i]);

    }

    // L[i] now stores increasing sub-sequence of

    // arr[0..i] that ends with arr[i]

    vector<int> max = L[0];

    // LIS will be max of all increasing sub-

    // sequences of arr

    for (vector<int> x : L)

        if (x.size() > max.size())

            max = x;

    // max will contain LIS

    printLIS(max);

}

Note that the time complexity of the above Dynamic Programming (DP) solution is O(n^2)

eg:-1 Input:  [10, 22, 9, 33, 21, 50, 41, 60, 80] Output: [10, 22, 33, 50, 60, 80] OR [10 22 33 41 60 80] or any other LIS of same length.

eg:-2

Let arr[0..n-1] be the input array. We define vector L such that L[i] is itself is a vector that stores LIS of arr that ends with arr[i]. For example, for array [3, 2, 6, 4, 5, 1],

L[0]: 3 L[1]: 2 L[2]: 2 6 L[3]: 2 4 L[4]: 2 4 5 L[5]: 1 

Therefore for an index i, L[i] can be recursively written as –

L[0] = {arr[O]} L[i] = {Max(L[j])} + arr[i] where j < i and arr[j] < arr[i] and if there is no such j then L[i] = arr[i]

Output:

 2 4 5