How to find the length of the longest upsequence in an unsorted array of integers?

Hi, everyone. I have a school java exercise, but i am not sure whether my method for this question is correct.

Question is :

An upsequence is any series of non-decreasing numbers. In a file called LongestUpsequence.java write a public class of the same name containing a method with the signature:

public int maxLength(int [] a);

to find the length of the longest upsequence in an unsorted array of integers. If the array is of length zero then maxLength must return zero. Use the fastest algorithm you can devise for doing this.

As an example of how the code should work, the driver code:

LongestUpsequence mySeq = new LongestUpsequence();

int [] myArray = {5,-11,2,3,14,5,-11,2};

System.out.println(mySeq.maxLength(myArray));

should print the number, 4 because the longest upsequence is -11,2,3,14.

My coding is:

Code:

`public class LongestUpsequence{`

public static void main (String[] args) {

LongestUpsequence mySeq = new LongestUpsequence();

int [] myArray = {5,-11,2,3,14,5,-11,2};

System.out.println(mySeq.maxLength(myArray));

}

public int maxLength(int [] a){

int longestUpsequence=0;

for(int i=1;i<a.length;i++){

if(a[i]>=a[i-1]){

longestUpsequence++;

}

}

if(a.length==0){

return 0;

}

else{

return longestUpsequence;

}

}

}

Because i need to submit my coding to website, then the system will auto mark my answer, but until now my result is still zero. Anyone can give me some suggestions or another method for this question?

Thanks very much!!

Re: How to find the length of the longest upsequence in an unsorted array of integers

First, arrays start indexing at zero. Second, you need to find the start of all possible upsequences in the array. And then return the longest one of those. Keep in mind that the next upsequence begins as soon as the current one fails. Example:

int[] v = new int[]{1,2,4,6,2,3,1,4,5);

The first upsequence starts at index# 0

The second starts at index#4

the third upsequence starts at index #6

Regards,

Jim

Re: How to find the length of the longest upsequence in an unsorted array of integers

Hi,Jim

For this question, can i use the method of sort to solve the problem? Could you give me some example?

Thanks!

Re: How to find the length of the longest upsequence in an unsorted array of integers

Quote:

can i use the method of sort to solve the problem?

Suppose you took the series and sorted it, how would you go about finding the longest sequence in the original series?

---

In general this sort of problem is best solved by stepping away from the computer. And mentally stepping away from Java code.

Instead *think* about how you would find the longest nondecreasing sequence given a whole bunch of numbers in some random order. To sharpen your thinking take a couple of dozen small pieces of paper and write single digit numbers on them. Arrange them into a line and then determine the size of the longest nondecreasing sequence.

Test your ideas. For instance when you have the pieces of paper in a line, sort them and see if that helps. That will answer you question about whether you can use sorting to solve this problem.

Only once you have a plan (one that is clear enough for you to be able to express here) should you start coding.