Problem 5. (30 points) Given an array A {ai.a2, , an} of integers, we say that a

Question

Problem 5. (30 points) Given an array A {ai.a2, , an} of integers, we say that a subsequence {ail, ai2, , aic} is (monotonically) increasing if for every is4, we have ai, ait. Given an array A of size n, we want to compute the length of the longest increasing subsequence (LIS) in A. For instance, if A- 9,5, 2,8,7,3, 1,6, 4) the length of the LIS is 3, because (2,3,4) (or (2,3,6)) are LIS of A. Give a O(n2) dynamic programming algorithm for this problem1. Analyze the time- and space-complexity of your solution.

Explanation / Answer

import java.util.Arrays;

class Main{
    public static void main(String[] args) {
        int A[] = {9,5,2,8,7,3,1,6,4};
        //dp[i] stores the length of the longest increasing subsequence starting from index i
        int dp[] = new int[A.length];
        //Initially LIS is 1
        Arrays.fill(dp, 1);
        int ans = 1;
        //Iterate from backwards
        for(int i=A.length-2;i>=0;i--){
            int max = 0;
            //Check if the number is greater thatn A[i] and find maximum LIS for all elements which are
            //Greater than A[i;
            for(int j=i+1;j<A.length;j++){
                if(A[j]>A[i]){
                    max = Math.max(max, dp[j]);
                }
            }
            //Update dp
            dp[i] = 1+max;
            //Calculate the answer obtained so far
            ans = Math.max(ans, dp[i]);
        }
        System.out.println(ans);
    }
}

OUTPUT :

3

----------------------------------

Time complexity of the program is O(N^2) Since we are running two loops.

Space complexity is O(N)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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