Question

Suppose you are given an array of n integers ai, az, ..., 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?

Answer 1

Hello Student!

I am happy to help you!

If you look closely, the following question seems to be longest Increasing Subsequence(LIS).

a) Optimal Substructure : A problem can be described to be in optimal substructure property if optimal solution solution of the given problem can easily be attained by using optimal solution of the subproblem.

           lis(3)
         /     |     
      lis(2)  lis(1)   
       /           
   lis(1) 

Now, In this problem what will be the subproblems, which can give the optimal solution?

Given an array, if we are able to know that at particular point the longest increasing subarray is of length 'x' then we can utilise this concept and formulate further solutions. And how can we do it?

For ex : A1, A2, A3, A4, A5, A6, A7 are the elements of an array.

Now, at A4 it is given that the longest increasing subarray is size of 'x' where x is less than 4. Now at A5, if A5 is greater than A4 then we can say the new longest increasing subsequence length till x can be x+1 because A5 > A4.

So, that's how we can utilise the concept of optimal substrucre property.

b) Pseudo code :

// Function for LIS

int LIS (int arr[], int n)

int dp[n];

for i = 0 to n

dp[i] = 1 // because a single element can be described as increasing because it is neither greater than // anyone nor it is smaller than anyone

end

for i = 0 to n

for j = 0 ; j < i

if dp[i] < dp[j]+1 && arr[i] < arr[j]

dp[i] = dp[j]+1

end

int ans = INT_MIN;

for i = 0 to n

ans = max ( ans , dp[i]);

return ans;

Time complexity of the following algorithm will comes out to be - O(n²)

c) Test Case Example :

Input : 5,1,6,7,2,8,3,4

arr = 5 1 6 7 2 8 3 4

dp =1 1 1 1 1 1 1 1 // Initializing it by 1

Now, if we apply the condn for all i and j where dp[i] < dp[j]+1 && arr[i] < arr[j]

then, dp table comes out to be-

dp =1 1 2 3 2 4 3 4

Now, there exists two optimal answer both of them of size 4. The subsequence are - {1, 2, 3, 4} and {5, 6, 7, 8}

It will give the length 4 as the output for {1, 2, 3, 4} because it find max length where max > dp[i]

Another Example :

arr = 1 3 4 9 2 3 4 10 6 11

dp = 1 1 1 1 1 1 1 1 1 1

Now, if we apply the condn for all i and j where dp[i] < dp[j]+1 && arr[i] < arr[j]

then, dp table comes out to be-

dp = 1 2 3 4 2 3 4 5 5 6

In this case, the maximum length is 6. But, there could be two possibilites of subsequence. How?

{1, 3, 4, 9, 10, 11} and {1, 2, 3, 4, 10, 11}

Both are of size and both have size of 6. Now, our algorithm only finds the longest length of the subsequence it doesn't matters which sequence it is. So, it will print 6.

d) How can we use table to generate multiple solution

Both the cases given above had two optimal solution. But, both had different table structure. Now, how would we able to find whether there are multiple solutions to the problem or not.

If we observe closely.

Our dp table came out to be this -

dp =1 1 2 3 2 4 3 4

For case 1, now we know 4 (at position i) is the most optimal answer. We will find 3(at position j) in the left side of the array such that arr[i] > arr[j]. Similarly we will recursively computer for 3 to 2 and then 2 to 1. We will multiply the number of cases that exists.

For, first 4 we will go for the first encounterd 3 because 4 > 3 (these are values in array) and there is only one three which exists, so current solution will be (1x1..). Now for 2, we will look into the left side again, there exists only 1 case.. (1x1x1..) Now, for 1 there exists single case. So (1x1x1x1).

Now, for other value of 4. If we perform similary it comes out to be (1x1x1x1).

Adding both 1+1 = 2

Two different subsequences.

Thank you. Feel free to ask anything. Please upvote, if you like the answer. Thank you again.