Java language only, and please make sure that it works. Write a method named lon
ID: 662705 • Letter: J
Question
Java language only, and please make sure that it works.
Write a method named longestSortedSequence that accepts an array of integers as a parameter and that returns the length of the longest sorted (nondecreasing) sequence of integers in the array. For example, if a variable named array stores the following values:
then the call of longestSortedSequence(array) should return 4 because the longest sorted sequence in the array has four values in it (the sequence -3, 0, 14, 207). Notice that sorted means nondecreasing, which means that the sequence could contain duplicates. For example, if the array stores the following values:
Then the method would return 5 for the length of the longest sequence (the sequence 3, 5, 5, 5, 8). Your method should return 0 if passed an empty array.
Explanation / Answer
Copy the below code inside your class.
private static class PairHolder<T> {
int start = -1;
int end = -1;
int weight = -1;
PairHolder(int start, int end) {
this.start = start;
this.end = end;
this.weight = start == -1 ? -1 : end-start+1;
}
int getSubArray(T[] arr) {
int sub=(Arrays.copyOfRange(arr, start, end+1).length);
return sub;
}
@Override
public String toString() {
return "[" + start + ", " + end + ", weight: " + weight + "]";
}
}
public static <T extends Comparable<? super T>> int longestSortedSequence(T[] chain) {
if(chain.length==0)
{
return 0;
}
int start = -1, end = -1;
PairHolder<T> longest = new PairHolder<T>(-1, -1);
for (int i = 0; i < chain.length - 1; i++) {
if (start == -1) {
start = i;
end = i;
}
if (chain[i+1].compareTo(chain[i]) == -1 ) {
if (end-start+1 > longest.weight) {
longest = new PairHolder<T>(start, end);
}
start = -1; end = -1;
continue;
}
end = i+1;
}
if (end-start+1 > longest.weight) { //corner case where last element of chain is also end of array
longest = new PairHolder<T>(start, end);
}
return(longest.getSubArray(chain));
}
---------------------------------------------------------------------------------------------------------------------------------------------------
Below is the whole program with Class declared and with main method declared. Use this to test the method longestSortedSequence.
Class Name : Sort
import java.util.Arrays;
public class Sort {
private static class PairHolder<T> {
int start = -1;
int end = -1;
int weight = -1;
PairHolder(int start, int end) {
this.start = start;
this.end = end;
this.weight = start == -1 ? -1 : end-start+1;
}
int getSubArray(T[] arr) {
int sub=(Arrays.copyOfRange(arr, start, end+1).length);
return sub;
}
@Override
public String toString() {
return "[" + start + ", " + end + ", weight: " + weight + "]";
}
}
public static <T extends Comparable<? super T>> int longestSortedSequence(T[] chain) {
if(chain.length==0)
{
return 0;
}
int start = -1, end = -1;
PairHolder<T> longest = new PairHolder<T>(-1, -1);
for (int i = 0; i < chain.length - 1; i++) {
if (start == -1) {
start = i;
end = i;
}
if (chain[i+1].compareTo(chain[i]) == -1 ) {
if (end-start+1 > longest.weight) {
longest = new PairHolder<T>(start, end);
}
start = -1; end = -1;
continue;
}
end = i+1;
}
if (end-start+1 > longest.weight) { //corner case where last element of chain is also end of array
longest = new PairHolder<T>(start, end);
}
return(longest.getSubArray(chain));
}
public static void main(String[] args) {
Integer[] arr = {17, 42, 3, 5, 5, 5, 8, 2, 4, 6, 1, 19};
System.out.println(longestSortedSequence (arr));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.