finding maximum contiguous sub-sequence in Array

the maximum value of the subsequence && the sub-sequence it se

Page 1 of 1

2 Replies - 6044 Views - Last Post: 31 October 2010 - 06:19 AM Rate Topic: -----

#1 No Signal X  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 nahsor  Icon User is offline

  • New D.I.C Head

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

Re: finding maximum contiguous sub-sequence in Array

Posted 31 October 2010 - 06:19 AM

View Postnahsor, 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 :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1