Suppose you are given an array of n integers a 1 , a 2 , …. a n. You need to fin

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, 30). 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

As per your requirement i have written solution which fulfill all your requirements please follow it step by step.

(a) Optimal Substructure:

Call the given exhibit as A = [a1, a2, a3, ........ an]. Give L(i) a chance to signify the length of longest non-diminishing arrangement finishing at index i with the end goal that ai is the last component.

At that point, L(i) can be recursively composed as:

L(i) = 1 + max(L(j)), Normally where 1 <= j < i and aj <= ai;

what's more, L(i) = 1, actually here when no such index j exist.

To locate the longest non-diminishing grouping for the given exhibit, we have to return max(L(i)) where 1 <= i <= n.

Accordingly, we see the optimal substructure property is fulfilled for this issue.

(b) Pseudocode and Time Complexity

Next we will write Pseudocode and along with time complexity please follow it step by step clearly

function(array A, length n)

for i E [1 . . n]

L[i] = 1

for j E [1, i-1]

if A[j] <= A[i]

L[i] = max(L[i], 1+L[j])

return maximum of L[1 . . n]

Time Complexity: Actually by above algorithm which we have written clearly show that does [constant*n*(n-1)/2] operations atlast which gives the asymptotic time complexity of O(n^2).

(c) Example
------------

(Example 1)

Input: A = {50, 3, 10, 7, 40, 80}

L = {1, 1, 2, 2, 3, 4}

Expected output: max(L[1...n]) = 3,

Actually here possible longest non-diminishing subsequence is {3, 7, 40, 80}

(Example 2)

Input: A = {3, 10, 2, 1, 20}

L = {1, 2, 1, 1, 3}

Expected output: max(L[1...n]) = 3,

Actually here possible longest non-diminishing subsequence is {3, 10, 20}

(d) If the appropriate response shows up in the dynamic programming table more than once, that is an assurance that in excess of one optimal arrangement exists. Else, we should check utilizing the list where the most extreme shows up. Assume the appropriate response shows up on record i in L. At that point, we simply need to check if there are in excess of one component A[j] for 1 <= j < i with the end goal that A[j] <= A[i].

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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