Create a program that will read the data for a two-dimensional integer array fro
ID: 3662885 • Letter: C
Question
Create a program that will read the data for a two-dimensional integer array from a file. Using this array, your program is to determine the longest increasing path within the array starting from an arbitrary starting point - that is, the longest path can start from any element within the array. Additionally, your program will find the longest incrementally increasing path within the array starting from an arbitrary starting point. In the event that two longest paths exist (both the same length), the path with the highest total value of elements will be selected. An increasing path is one in which the subsequent value in the path is always larger than its predecessor (example 2-4-5-8-12- 20). An incrementally increasing path is one in which the subsequent value in the path is exactly one larger than its predecessor (example 3 - 4 - 5 - 6). For both, only moves up, down, left and right are permitted. Several test data files are provided to help you test your program. Sample output for the first two files are shown below. Format your output to match these samples.Explanation / Answer
public class LongestIncreasingSubsequence {
public void findSubsequence(int[] arrA) {
int[] LIS = new int[arrA.length];
for (int i = 0; i < arrA.length; i++) {
int max = -1;
for (int j = 0; j < i; j++) {
// check if previous elements > current element
if (arrA[i] > arrA[j]) {
// update the max from the previous entries
if (max == -1 || max < LIS[j] + 1) {
max = 1 + LIS[j];
}
}
}
if (max == -1) {
// means none of the previous element has smaller than arrA[i]
max = 1;
}
LIS[i] = max;
}
// find the max in the LIS[]
int result = -1;
int index = -1;
for (int i = 0; i < LIS.length; i++) {
if (result < LIS[i]) {
result = LIS[i];
index = i;
}
}
// Print the result
// Start moving backwards from the end and
String path = arrA[index] + " ";
int res = result-1;
for (int i = index-1; i >= 0; i--) {
if(LIS[i]==res){
path = arrA[i] + " " + path;
res--;
}
}
System.out.println(the length of this path is: " + result);
System.out.println("the longest increamentall path is: " + path);
}
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
System.out.println(“enter file name”);
String filename= scanner.next();
Int[] A= getIntsFromFile(filename);
LongestIncreasingSubsequence i = new LongestIncreasingSubsequence();
i.findSubsequence(A);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.