Maximal Subsequence Problem

Given a sequence of ‘n’ integers where 1<n<=25. A maximal subsequence is the subsequence with the highest sum. Thus for the sequence given below:

          -1,2,8,-7,3,5,-20,2,1

The maximal sequence runs from 2nd number to 6th number (sum of the number is 11), since no other subsequence has a higher sum.

Write a program which reads a sequence of ‘n’ number and find it’s maximal subsequence. Input consists of a number ‘n’ followed by n numbers. The sequence will have positive sum for the maximal subsequence. Output should consists of the start and end indices of the maximal subsequence and it’s resulting sum. If more than one maximal subsequence exist then print all of them.

        Sample Input

          9

          -1,2,8,-7,3,5,-20,2,1

          Sample Output

         Maximal Subsequence:

          Starting Index : 2

          Ending Index   : 6

          Sum            : 11

        Test your program for following data:

          15

          1,2,5,4,-6,20,7,8,11,12,-2,-4,1,2,9

Answer: import java.io.*;
class MaximalSubseq
{
private static int sumOf(int arr[], int start, int stop)
{
int sum=0;
for(int i=start;i<=stop;i++)
sum+=arr;
return sum;
}
public static void main()
{
//        int arr[]={-1,2,8,-7,3,5,-20,2,1};
int arr[]={1,2,5,4,-6,20,7,8,11,12,-2,-4,1,2,9};
int high=0,sum=0,start=0,end=0;
for(int i=0;i<arr.length;i++)
{
for(int j=arr.length-1;j>=0;j–)
if(i>0 && j>0 && j<arr.length-1 && i<arr.length-1) // Check        for SubSequence
{
sum=sumOf(arr,j,i); // Takes the Sum For The starting and ending limit
if(high<sum)
{
high=sum;
start=j+1; // Finds The Start Limit
end=i+1; // Finds The End Limit
}
}
sum=0;
}
System.out.print(“MAXIMAL SUBSEQUENCE”);
System.out.print(“\nStarting Index :”+start);
System.out.print(“\nEnding Index :”+end);
System.out.print(“\nSum : “+high);
}
}

Leave a Comment