Results 1 to 2 of 2
  1. #1
    Ba Im is offline Member
    Join Date
    Mar 2011
    Posts
    1
    Rep Power
    0

    Default need help with max subsequence

    Java Code:
    import java.util.*;
    import java.io.*;
    
    class maxSum{
    	public static int[] maxSubSum( int [ ] a )
    	{
    		int maxSum = 0;
    		int thisSum = 0;
    		int[] index = {0,-1};
    
    		for( int i = 0, j = 0; j < a.length; j++ )
    		{
    			thisSum += a[ j ];
    
    			if( thisSum > maxSum )
    			{
    				maxSum = thisSum;
    				index[0]= i;
    				index[1]   = j;
    			}
    			else if( thisSum < 0 )
    			{
    				i = j + 1;
    				thisSum = 0;
    			}
    		}		
    		return index;
    	}
    	public static void main(String[] args) {
    		try{
    			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    			StringTokenizer data;
    			Integer bus = Integer.parseInt(br.readLine());
    			int[] dataarr = new int[bus];
    			int[] index = {0,-1};
    			data = new StringTokenizer(br.readLine()," ");
    			for(int ii = 0; ii < bus; ii++)
    				dataarr[ii] = Integer.parseInt(data.nextToken());
    			index = maxSubSum(dataarr);
    			System.out.println("Max sum subseq from index:  "+index[0]+" to "+index[1] );
    		}
    		catch(Exception e){}
    		}
    }
    code above print indexes of max contiguous subsequence sum. the problem is it return the first found subseq, theres a probability of more than one subsequence with max sum value. so can any one help me to find the index of max sum with longest subsequence...the only thing i thought is brute force,,:p
    I found a code here, but totaly know nothing 'bout REXX...
    Last edited by Ba Im; 03-01-2011 at 12:15 PM.

  2. #2
    ozzyman's Avatar
    ozzyman is offline Senior Member
    Join Date
    Mar 2011
    Location
    London, UK
    Posts
    797
    Blog Entries
    2
    Rep Power
    4

    Default

    by "max contiguous subsequence sum" you mean any sequence of 2 contiguous numbers in the array?

    I would add ALL sums to an arrayList e.g.
    Java Code:
    java.util.List<Int> maxSum = new java.util.ArrayList<Int>();
    //because we're adding sequence of 2's, we dont need i to start at the last element, so we use a.length-1
    for (int i=0; i<(a.length-1);i++) {
      int thisSum = a[i] + a[i+1];
      maxSum.add(thisSum);
    }
    Now that you have a List of ALL subsequence sums you can iterate through that list and find which one is the highest by sorting the list e.g.

    Java Code:
    //convert List to Array and sort ascending
    int[] newArray = maxSum.toArray(new Int[maxSum.size()]);
    java.util.Arrays.sort(newArray);
    
    //take max from last item in array
    int theMax = newArray[newArray.length-1];
    
    //to return the index, search for max value in maxSum list
    int maxIndex = 0;
    for (int i:maxSum) {
      if (i == theMax) {
        maxIndex = maxSum.indexOf(i);
      }
    }

Similar Threads

  1. Maximum subsequence
    By dxg in forum New To Java
    Replies: 12
    Last Post: 09-25-2010, 06:40 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
  •