# Thread: need help with max subsequence

1. Member
Join Date
Mar 2011
Posts
1
Rep Power
0

## 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{
StringTokenizer data;
int[] dataarr = new int[bus];
int[] index = {0,-1};
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. 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];
}```
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);
}
}```

#### Posting Permissions

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