Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By pbrockway2

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

  1. #1
    hjxlpp is offline Member
    Join Date
    May 2013
    Posts
    17
    Rep Power
    0

    Default 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:
    Java 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!!

  2. #2
    jim829 is online now Senior Member
    Join Date
    Jan 2013
    Location
    United States
    Posts
    3,378
    Rep Power
    5

    Default 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
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  3. #3
    hjxlpp is offline Member
    Join Date
    May 2013
    Posts
    17
    Rep Power
    0

    Default 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!

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

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

    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.
    jim829 likes this.

Similar Threads

  1. Replies: 10
    Last Post: 05-17-2013, 01:20 PM
  2. Length of an Array: length() or just length ?
    By Jack_Tauson_Sr in forum New To Java
    Replies: 8
    Last Post: 03-18-2013, 08:16 PM
  3. cannot find symbol - variable length
    By walsby14 in forum New To Java
    Replies: 1
    Last Post: 07-16-2012, 01:38 PM
  4. Find Special String length in jdk1.6 on Unix
    By ganeshmore in forum New To Java
    Replies: 1
    Last Post: 06-13-2012, 10:27 AM
  5. java longest word in array
    By mayhewj7 in forum New To Java
    Replies: 10
    Last Post: 04-24-2009, 01:39 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •