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:


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



          Sample Output

         Maximal Subsequence:

          Starting Index : 2

          Ending Index   : 6

          Sum            : 11

        Test your program for following data:



Answer: import*;
class MaximalSubseq
private static int sumOf(int arr[], int start, int stop)
int sum=0;
for(int i=start;i<=stop;i++)
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
start=j+1; // Finds The Start Limit
end=i+1; // Finds The End Limit
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