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


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

Popular posts from this blog

Getting started with Deep Learning Caffe Framework - Fastest way(Installation +Web Demo)

Sudoku using dancing link - Java implementation

OpenCV 2.4.9 JAVA/CPP/Python Installation in Ubuntu 14.04