Create a program that will read the data for a two-dimensional integer array fro

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.

*** here is the out put *** it should be the same

Enter name of problem file: testData1.txt

[ 3, 4, 5]
[ 9, 6, 7]
[ 2, 1, 8]

The longest increasing path with maximum total is: 3-4-6-7-8

The length of this path is 5 and the total of the values is 28.

The longest incrementally increasing path with maximum total is: 6-7-8

The length of this path is 3 and the total of the values is 21.

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--;
}
}
int val=0;
for(int i=0;i<LIS.length)
{
val=val+LIS[i];
}

System.out.println(The length of this path: " + result);
System.out.println(the total of the values: " + val);
System.out.println("The longest increasing path with maximum total 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

Navigate

• Browse (All)
• Browse C
• Subjects

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