use python 3 Write a function named longest_sorted_sequence that accepts a list
ID: 3699106 • Letter: U
Question
use python 3
Write a function named longest_sorted_sequence that accepts a list of integers as a parameter and that returns the length of the longest sorted (nondecreasing) sequence of integers in the list. For example, if a variable named list stores the following values:
then the call of longest_sorted_sequence(list) should return 4 because the longest sorted sequence in the list 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 list stores the following values:
Then the function would return 5 for the length of the longest sequence (the sequence 3, 5, 5, 5, 8). Your function should return 0 if passed an empty list. Your function should return 1 if passed a list that is entirely in decreasing order or contains only one element.
Constraints: You may not use any auxiliary data structures (lists, strings, etc.) to solve this problem. Your function should not modify the list that is passed in.
Explanation / Answer
PYTHON PROGRAM:
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) {
longest = new PairHolder<T>(start, end);
}
return(longest.getSubArray(chain));
}
For ongestSortedSequence method .
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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.