Suppose you are given an array of n integers a1, a2, .., an. You need to find ou

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, 30) is 5 and one such sub-array is 5, 10, 13, 19, 303. 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?

Explanation / Answer

a.)  

Let L(i) be the length of the Longest Increasing Subsequence ending at index i such that A[i] is the last element of the Longest Increasing Subsequence .

L(i) can be recursively written as:
L(i) = 1 + max( L(j) ) , 0 < j < i and A[j] < A[i]; or

L(i) = 1, if no such j exists.

Thus this problem follows optimal substructure property. It can easily be broken down into smaller problems.

b.) PSEUDO CODE :

int lis( int arr[], int n ) // arr is the actual array

{ int *lis, i, j, max = 0;

    lis = (int*) malloc ( sizeof( int ) * n );

    for (i = 0; i < n; i++ )    /* Initialize LIS values for all indexes */

        lis[i] = 1;

    for (i = 1; i < n; i++ )    /* Computing the lis array*/

        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++ )     /* Pick maximum of all LIS values */

        if (max < lis[i])

            max = lis[i];

return max;

}

Since the loop in the functions runs n*n times . Hence the asymptotic run time of this algorithm is O(n2).

c.) example 1 : A = { 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2 };

Here we have 2 subarrays with length 7 :

1. 1, 12, 23, 52,61, 69, 70

2. 1, 7, 11, 31, 61, 69, 70.

But the algorithm always finds the largest of all so this case covers up automatically even if there are 2 sub arrays with same longest length.

example 2 :

A = { 90, 12, 14, 0, 23, 11, 52, 31, 68, 72, 2, 84 };

d.) from the dp linear table,if we find two same digits continuously in the LIS array (except 1) we can say that we have more than 2 arrays.

like in example 2, no. 4 is associated with 52 as well 31, so we can have either 31 or 52 in the array for which the longest value remains same.

A[] 1 12 7 0 23 11 52 31 61 69 70 2 LIS[] 1 2 2 1 3 3 4 4 5 6 7 2

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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