Below is the code attached to calculate the max. subsequence of length atleast l in O(n) time.This algorithm works as follows:-
1.) calculate sum of first array L elements. and set running sum & maxsum equal to sum.
2.) for each element after L elements
a) calculate sum=sum+array[i]-array[i-L];
b) calculate runningsum=runningsum+array[i];
c) update runningsum if sum is greater than running sum.
d) update maxsubsequence if runningsum is greater than max subsequence.
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,runningsum=0;
for(i=0;i<arrLength;i++){
if((i+1)<=lenOfSubSequence){
sum=sum+array[i];
maxSubsquence=sum;
runningsum=sum;
}else{
sum=sum+array[i]-array[i-lenOfSubSequence];
runningsum=runningsum+array[i];
}
if(sum>runningsum){
runningsum=sum;
}
if(runningsum>maxSubsquence){
maxSubsquence=runningsum;
}
}
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));
}
}
_________________________________________________________________________________
Comments
Post a Comment