Results 1 to 6 of 6
  1. #1
    caseballs is offline Member
    Join Date
    Feb 2011
    Posts
    3
    Rep Power
    0

    Default Help with a largest sub-vector problem

    I am a noob so be gentle.


    Have to create a program to find the largest sub vector from a text file, the contents of which are below:

    6,94,-63,-41,20,5,-61,83,-14,-50,
    36,30,32,51,96,72,99,23,-59,-23,


    I have a program written to do this but it returns 439 instead of 458 as the largest sub vector and I can't figure out why, it also prints out 0 and 100 before the 438 and I don't know why either. Any guidance or help is much appreciated.

    Code below:

    Java Code:
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.StringTokenizer;
    
    
    public class largestSubVector {
    
    
        public static void main(String[] args) throws IOException
        {
    
            int [] data = new int [20];
            String line = null;
    
    
            File file = new File("vector20.txt");
            BufferedReader bufRdr  = new BufferedReader(new FileReader(file));
    
            while((line = bufRdr.readLine()) != null)
            {
                StringTokenizer st = new StringTokenizer(line,",");
                int i = 0;
                while (st.hasMoreTokens())
                {
    
                    data[i] = Integer.parseInt(st.nextToken());
                    //System.out.println(data[i]);
                    i++;
                }
    
                int this_sum = 0, max_sum = 0;
                int n = 20;
    
                for (int j = 0; j < n; j++)
                    {
                        this_sum += data[j];
    
                        if (this_sum > max_sum) {
                            max_sum = this_sum;
                        } else
                            if (this_sum < 0) {
                                this_sum = 0;
                            }
                    }
    
                System.out.println(max_sum);
    
            }
    
        }
    }

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by caseballs View Post
    Have to create a program to find the largest sub vector from a text file, the contents of which are below:

    6,94,-63,-41,20,5,-61,83,-14,-50,
    36,30,32,51,96,72,99,23,-59,-23,


    I have a program written to do this but it returns 439 instead of 458 as the largest sub vector and I can't figure out why
    Can you please define the problem? What is considered to be a 'largest sub vector'?

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    caseballs is offline Member
    Join Date
    Feb 2011
    Posts
    3
    Rep Power
    0

    Default

    Ok I got rid of the 0 and 100 problem just some code inside the while loop that should have been outside. Updated code below:

    Java Code:
    package Assignment1;
    
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileReader;
    import java.io.IOException;
    import java.util.StringTokenizer;
    
    
    public class largestSubVector {
    
    
        public static void main(String[] args) throws IOException
        {
    
            int [] data = new int [20];
            String line = null;
    
    
            File file = new File("vector20.txt");
            BufferedReader bufRdr  = new BufferedReader(new FileReader(file));
    
            while((line = bufRdr.readLine()) != null)
            {
                StringTokenizer st = new StringTokenizer(line,",");
                int i = 0;
                while (st.hasMoreTokens())
                {
    
                    data[i] = Integer.parseInt(st.nextToken());
                    //System.out.println(data[i]);
                    i++;
                }
    
              
            }
    
            int this_sum = 0, max_sum = 0;
                int n = 20;
    
                for (int j = 0; j < n; j++)
                    {
                        this_sum += data[j];
    
                        if (this_sum > max_sum) {
                            max_sum = this_sum;
                        } else
                            if (this_sum < 0) {
                                this_sum = 0;
                            }
                    }
    
                System.out.println(max_sum);
    
        }
    }

    Quote Originally Posted by JosAH View Post
    Can you please define the problem? What is considered to be a 'largest sub vector'?

    kind regards,

    Jos

    The problem wasn't well explained to me so I'm not sure if I will be able to explain it well to you. But for the numbers above the largest sub vector is the underlined values:

    6,94,-63,-41,20,5,-61,83,-14,-50,
    36,30,32,51,96,72,99,23,
    -59,-23,

    = 458


    So for example in my code the 100 was coming from the 6,94, which is 100 then the -63, -41 end that sub vector. Then the next sub vector is 20,5, = 25 then -61 ends that sub vector.


    I believe it's also called the largest subsequence problem(??)

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by caseballs View Post
    The problem wasn't well explained to me so I'm not sure if I will be able to explain it well to you. But for the numbers above the largest sub vector is the underlined values:

    6,94,-63,-41,20,5,-61,83,-14,-50,
    36,30,32,51,96,72,99,23,
    -59,-23,

    = 458


    So for example in my code the 100 was coming from the 6,94, which is 100 then the -63, -41 end that sub vector. Then the next sub vector is 20,5, = 25 then -61 ends that sub vector.

    I believe it's also called the largest subsequence problem(??)
    The sum of the consecutive positive numbers in your second example is 439; I really don't understand your explanation, sorry.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    caseballs is offline Member
    Join Date
    Feb 2011
    Posts
    3
    Rep Power
    0

    Default

    Quote Originally Posted by JosAH View Post
    The sum of the consecutive positive numbers in your second example is 439; I really don't understand your explanation, sorry.

    kind regards,

    Jos

    can you explain to me how you are getting 439?


    83 -14 -50 + 36 + 30 + 32 + 51 + 96 + 72 + 99 + 23 = 458?


    edit: Nevermind I see where you are getting it now.

    Now that I see where the 439 is coming from I should be able to fix this myself, will post the updated code in case anybody wants to see it. Thanks for your help, you indirectly got me to solve it lol. :)
    Last edited by caseballs; 02-13-2011 at 08:40 PM.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,560
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by caseballs View Post
    can you explain to me how you are getting 439?


    83 -14 -50 + 36 + 30 + 32 + 51 + 96 + 72 + 99 + 23 = 458?


    edit: Nevermind I see where you are getting it now.

    Now that I see where the 439 is coming from I should be able to fix this myself, will post the updated code in case anybody wants to see it. Thanks for your help, you indirectly got me to solve it lol. :)
    I simply added all consecutive positive numbers in your second example (or the second line of your example). I still don't understand your problem ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. Vector Problem
    By osmaavenro in forum New To Java
    Replies: 14
    Last Post: 10-01-2010, 11:03 AM
  2. Problem with Vector
    By banhbaochay in forum New To Java
    Replies: 9
    Last Post: 04-01-2010, 05:01 PM
  3. Vector problem
    By Ace_Of_John in forum New To Java
    Replies: 1
    Last Post: 01-27-2008, 08:53 PM
  4. ArrayList problem (finding largest no)
    By bugger in forum New To Java
    Replies: 3
    Last Post: 12-12-2007, 12:47 PM
  5. vector problem
    By mambo_jumbo in forum New To Java
    Replies: 1
    Last Post: 11-17-2007, 10:44 PM

Posting Permissions

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