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