[No Signal X]

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);
		}	

}

[nahsor]

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

[nahsor]

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