# finding maximum contiguous sub-sequence in Array

Page 1 of 1

## 2 Replies - 9442 Views - Last Post: 31 October 2010 - 06:19 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=197455&amp;s=5655e39798c1ddcada7980ebcb58c956&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 No Signal X

Reputation: 0
• Posts: 5
• Joined: 29-October 10

# finding maximum contiguous sub-sequence in Array

Posted 29 October 2010 - 01:53 PM

hi ,, I need ur help here

i'm writing brute force algorithm to find the maximum contiguous sub-sequence in an array

the program must display the maximum value & the sub-sequence ,,, I did it but still does not display the sub-sequence. it displays only the max value.

for example: For the array {5,-8,-4,50,-1,10,-9}, the answer is {50,-1,10} whose sum is 59

```import java.util.Scanner;

public class Algorithm {

public static void main(String[] args) {

Scanner console = new Scanner(System.in);
System.out.println("Size: ");
int s=console.nextInt();
Algorthim obj= new Algorthim();

int[] array=new int[s];
System.out.println("enter numbers");

for(int i=0; i<array.length; i++){
array[i]=console.nextInt();
}obj.FindSeq(array,array.length);
}
public void FindSeq (int A[], int n){
int [] arr2 = new int [n*(n-1)];
int sum =0;
int max=0;
for(int i=0; i<n; i++){
for(int j=i; j<=i; j++){
sum=sum+A[j];
System.out.println("sum A["+j+"]= " +sum);
for(int c=0; c<=j; c++){
if(arr2[c]== 0){
arr2[c]=sum;
System.out.println("arr2["+c+"]="+arr2[c]);

}
if(arr2[c]> max)
max = arr2[c];

}
}
}System.out.println("max ="+max);
}

}
```

Is This A Good Question/Topic? 0

## Replies To: finding maximum contiguous sub-sequence in Array

### #2 nahsor

Reputation: 0
• Posts: 2
• Joined: 31-October 10

## Re: finding maximum contiguous sub-sequence in Array

Posted 31 October 2010 - 03:19 AM

Actually there is one confusion u want the max of the contiguous sub-sequence in array or the max value of the array

pls find the code below which i modified which will give the max value of the contiguous sub-sequence and also print the sub sequence.
```import java.util.Scanner;

public class Algorithm {

public static void main(String[] args) {

Scanner console = new Scanner(System.in);
System.out.println("Size: ");
int s=console.nextInt();
Algorithm obj= new Algorithm();

int[] array=new int[s];
System.out.println("enter numbers");

for(int i=0; i<array.length; i++){
array[i]=console.nextInt();
}obj.FindSeq(array,array.length);
}

public void FindSeq( int A[], int n)
{
int [][] arr2 = new int [n][n];
int i,j =0,loop=0;
while(loop<n)
{
for (i=loop; i< n; i++)
{
for (j=loop;j<=i+1&&j<n;j++)
{
arr2[loop][i]=arr2[loop][i]+A[j];

}

}
loop++;
}

int  p =0,q=0;
int maxval=arr2[0][0];
for(j=0;j<n;j++)
{

for(i=0;i<n-1;i++)
{
if(maxval<arr2[j][i+1])
{
maxval=arr2[j][i+1];
p=j;
q=i;
}

}
}
System.out.println("max of the contigous substring ="+maxval);
System.out.println("Sub Sequence is ");
for(i=p;i<p+q;i++)
System.out.print(A[i]+"\t");
}
}

```

This post has been edited by nahsor: 31 October 2010 - 03:27 AM

### #3 nahsor

Reputation: 0
• Posts: 2
• Joined: 31-October 10

## Re: finding maximum contiguous sub-sequence in Array

Posted 31 October 2010 - 06:19 AM

nahsor, on 31 October 2010 - 02:19 AM, said:

Actually there is one confusion u want the max of the contiguous sub-sequence in array or the max value of the array

pls find the code below which i modified which will give the max value of the contiguous sub-sequence and also print the sub sequence.
```import java.util.Scanner;

public class Algorithm {

public static void main(String[] args) {

Scanner console = new Scanner(System.in);
System.out.println("Size: ");
int s=console.nextInt();
Algorithm obj= new Algorithm();

int[] array=new int[s];
System.out.println("enter numbers");

for(int i=0; i<array.length; i++){
array[i]=console.nextInt();
}obj.FindSeq(array,array.length);
}

public void FindSeq( int A[], int n)
{
int [][] arr2 = new int [n][n];
int i,j =0,loop=0;
while(loop<n)
{
for (i=loop; i< n; i++)
{
for (j=loop;j<=i+1&&j<n;j++)
{
arr2[loop][i]=arr2[loop][i]+A[j];

}

}
loop++;
}

int  p =0,q=0;
int maxval=arr2[0][0];
for(j=0;j<n;j++)
{

for(i=0;i<n-1;i++)
{
if(maxval<arr2[j][i+1])
{
maxval=arr2[j][i+1];
p=j;
q=i;
}

}
}
System.out.println("max of the contigous substring ="+maxval);
System.out.println("Sub Sequence is ");
for(i=p;i<p+q;i++)
System.out.print(A[i]+"\t");
}
}

```

check this out if its work if dont ping me bk