Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 4 of 4

Thread: I have algorithm problem

  1. #1
    Junior Member
    Join Date
    Oct 2009
    Posts
    13
    Thanks
    2
    Thanked 0 Times in 0 Posts

    Default I have algorithm problem

    Here is the problem:

    Given a list of integers, A0, A2, ... , An-1, each of which may be

    positive or negative, find the sublist of integers Ai, ..., Aj which has

    the maximum sum of any sublist. If all the integers are negative,

    return 0.

    A sublist has to start at some position in the original list, finish at some later position and

    include every number which is in the original list between those positions. So, for

    example if the list is {10,-20,11,-4,13,3,-5,-17,2,15,1,-7,8} then the answer

    is 23 since this is the sum of the list {11,-4,13,3} and no other sublist has a higher

    sum. The answer is always at least 0, because the empty list is always a possible sublist,

    and its sum is 0.


    What I have done is

    import java.util.*;
     
    class Exercise6c
    {
    // Front end code for the problem set as Exercise 6
     
     public static void main(String[] args)
     {
      Scanner input = new Scanner(System.in);
      System.out.println("Enter some numbers (all on one line, separated by commas):");
      String line = input.nextLine();
      String[] numbers = line.split(",");
      int[] array = new int[numbers.length];
      for(int i=0; i<array.length; i++)
          array[i]=Integer.parseInt(numbers[i].trim());
      int highSum = highestSum(array);
      System.out.println("The highest sum of a sublist of the numbers is: "+highSum);
     }
     
     public static int highestSum(int[] a)
     {
      int sum = 0;
      int sm = 0;
      for(int i = 0; i < a.length; i++){
        for(int j = 1; j < a.length; j++){
           //  sum = a[i];
              for (int k = 0; k < (j-i)+1 ; k++){
                   sum = sum + a[i+k];
                   if (sum > sm ){
                       sm = sum ;
                   }
              }
        }
     
      }
       return sm ;
      // ... To be filled in ...
     }
     
    }

    just look at method highestSum.( Apprently one of the applications is stock market analysis.)
    Can anyone solve the problem of just altering the method highestSum, to find the solution to the task.
    Last edited by helloworld922; November 11th, 2009 at 07:12 PM. Reason: please use [code] tags


  2. #2
    Member
    Join Date
    Jul 2009
    Posts
    31
    Thanks
    3
    Thanked 6 Times in 5 Posts

    Default Re: I have algorithm problem

    pretty clean ;]

    works

    wow im getting good at this ;] only took 5 minutes

    public class sublist
    {
    int arr[] = {10,-20,11,-4,13,3,-5,-17,2,15,1,-7,8};
     
    public int highestSum(int[] a)
    {
    int max=0;
    int cycle;
     
    if(allNeg(a))
        return 0;
     
    //Shifts starting index by 1 every time the Ending index reaches its max (also shifts Ending index back to Starting index)
    for(int i =0; i< a.length; ++i) //defines Starting index
    {
        for(int j=i; j< a.length;++j) //defines Ending index
        {
        cycle=0;
     
            for(int k=i; k <=j ; ++k) //Sums from Starting index to Ending Index
            {
                cycle+=a[k];
     
            }
        if(cycle > max)
        max = cycle;
        }
    }
    return max;
    }
     
    private boolean allNeg(int[] a)
    {
    for(int i=0; i<a.length; ++i)
        if(a[i] >= 0)
            return false;
    return true;
    }
     
    }
    Last edited by rsala004; November 11th, 2009 at 08:13 PM.

  3. #3
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,318
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: I have algorithm problem

    The k loop does the job, but isn't necessary...
    //check for all negative...the check for the max series
    int sum = 0;
    for ( int i = 0, st = 0; i < a.length; i++, st = 0 ){
    	for ( int j = i; j < a.length; j++ ){
    		st += a[j];
    		if ( st > sum ){ sum = st;}
    	}
     
    }
    return sum;

  4. #4
    Member
    Join Date
    Jul 2009
    Posts
    31
    Thanks
    3
    Thanked 6 Times in 5 Posts

    Default Re: I have algorithm problem

    ah your right

Similar Threads

  1. Parsing By Prediction Algorithm(?)
    By benjamin in forum Collections and Generics
    Replies: 5
    Last Post: September 30th, 2009, 03:21 PM
  2. algorithm
    By AmmrO in forum Algorithms & Recursion
    Replies: 13
    Last Post: September 24th, 2009, 09:18 PM
  3. Insert sort algorithm
    By Alysosh in forum Algorithms & Recursion
    Replies: 1
    Last Post: May 26th, 2009, 09:28 AM