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));
  }

}

_________________________________________________________________________________

Comments

  1. This is subarray logic.
    Maximum sum subsequence = 2,3,4, =9

    ReplyDelete

Post a Comment