Problem 5. (30 points) Given an array A {ai.a2, , an} of integers, we say that a
ID: 3209690 • Letter: P
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)