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

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, 80} is 6 and one such sub-array is {5, 10, 13, 19, 70, 80}. 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.) Optimal Substructure:

Call the given array as A = [a1, a2, a3, ..... an]. Let L(i) denote the length of longest non-decreasing sequence ending at index i such that ai is the last element.

Then, L(i) can be recursively written as:

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

and L(i) = 1, when no such index j exist.

To find the longest non-decreasing sequence for the given array, we need to return max(L(i)) where 1 <= i <= n.

Thus, we see the optimal substructure property is satisfied for this problem.

b.) Pseudocode and Time Complexity

function(array A, length n)

for i [1 . . n]

L[i] = 1

for j [1, i-1]

if A[j] <= A[i]

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

return maximum of L[1 . . n]

Time Complexity: The above algorithm clearly does [constant*n*(n-1)/2] operations which gives us the assymtotic time complexity of O(n^2).

c.) Example

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

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

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

only possible longest non-decreasing subsequence is {3, 10, 20}

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

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

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

one possible longest non-decreasing subsequence is {3, 7, 40, 80}

d.) If the answer appears in the dynamic programming table more than once, that's a guarantee that more than one optimal solution exists. Otherwise, we will have to check using the index where the maximum appears. Suppose the answer appears on index i in L. Then, we just have to check if there are more than one element A[j] for 1 <= j < i such 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.