Let A = (a1, a2, ..., an) be a sequence of numbers. Another sequence Z = (z1, z2

Question

Let A = (a1, a2, ..., an) be a sequence of numbers. Another sequence Z = (z1, z2, ..., zm), m <= n is a subsequence of A if there exists a strictly increasing sequence (i1, i2, ..., ik) of indices of A such that for all j = 1, 2, ..., k, zj = Aij . More intuitively, the sequence Z is obtained by deleting some numbers from A without changing the order of the remaining numbers. For example, if A = (1, 3, 5, 7, 9, 11), then Z = (3, 9, 11) is a subsequence of A. Design an O(n2) dynamic programming algorithm to find the longest monotonically increasing subsequence of a sequence of n numb

Explanation / Answer

Please find my code.

/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;

class LMISub {

public void getLongestIncSub( int[] input) {
  
//create a result array
int[] result = new int[input.length];
  
for (int i = 0; i < input.length; i++) {
int maximum = -1;
for (int j = 0; j < i; j++) {
/*
if the previous elements is greater
that the current element
*/
if (input[i] > input[j]) {
   // update the value of maximum
if (maximum == -1 || maximum < result[j] + 1) {
maximum = 1 + result[j];
}
}
}
if (maximum == -1) {
/*
According to this none of the previous
element are smaller than the input[i] element
*/
maximum = 1;
}
result[i] = maximum;
}

int length = -1;
int index = -1;
for (int i = 0; i < result.length; i++) {
if (length < result[i]) {
length = result[i];
index = i;
}
}
  
// Start moving backwards from the end and
String sequence = input[index] + " ";
int temp = length - 1;
for (int i = index - 1; i >= 0; i--) {
if (result[i] == temp) {
sequence = input[i] + " " + sequence;
temp--;
}
}
  
System.out.print("Input Sequence: ");
for(int i=0; i<input.length; i++){
   System.out.print(input[i]+" ");
}
System.out.println();
  
//printing the Length of the desired sequence
System.out.println("Length: " + length);
  
//printing the Longest Mononotincally Increasing SubSequence
System.out.println("Longest Mononotincally Increasing SubSequence: " + sequence);
}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

// take the array as input from the user
int n = scan.nextInt();
int[] input = new int[n];
for (int i = 0; i < n; i++) {
input[i] = scan.nextInt();
}
  
//create an object of LMISub class
LMISub i = new LMISub();
// call the getLongestIncSub function
i.getLongestIncSub(input);
}
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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