### Algorithm to find Max. sub sequence of length exactly l in linear time

Below is the attached code to calculate max sub sequence of length l which is entered by user.Algorithm calculate the max subsequence in O(n) time.The logic are as follows:-

1.)Take two variable sum and maxsum.

2.)Run the algorithm till (i+1)<=l and calculate the sum.

3.)After when i+1)>l ,then it follows the recursion like this. sum(n)=sum(n-1)+array[i]-array[i-l] ,it shows sum of next elements of length l is equal to sum of previous l elements + current element - (first element in sum of previous element)

for an example:-

2 -1 -2 3 4

then it has following sum of length 3

1.) 2+(-1)+(-2) = -2

2.) (-1)+(-2)+3 = -1

3.) (-2)+3+4 = 5

max sub sequence is 5.

Please find the below code ,you can try and run the below code on

**http://www.compileonline.com/compile_c_online.php**

Happy coding

_________________________________________________________________________________

#include <stdio.h>

#include <string.h>

int findMaxSubsequence(int array[],int arrLength,int lenOfSubSequence){

int i,maxSubsquence,sum=0;

for(i=0;i<arrLength;i++){

if((i+1)<=lenOfSubSequence){

sum=sum+array[i];

maxSubsquence=sum;

}else{

sum=sum+array[i]-array[i-lenOfSubSequence];

}

if(sum>maxSubsquence){

maxSubsquence=sum;

}

}

return maxSubsquence;

}

main()

{

int arrLength,lenOfSubSequence,i;

printf("Enter Number of elements\n");

scanf("%d",&arrLength);

printf("Enter Length of subsequence\n");

scanf("%d",&lenOfSubSequence);

int array[arrLength];

for(i=0;i<arrLength;i++){

scanf("%d",&array[i]);

}

if(lenOfSubSequence>arrLength){

printf("No subsequence exist");

}else{

printf("Max Sum subsequence of length %d is %d",lenOfSubSequence,findMaxSubsequence(array,arrLength,lenOfSubSequence));

}

}

_________________________________________________________________________________

This is subarray logic.

ReplyDeleteMaximum sum subsequence = 2,3,4, =9