Skip to main content

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

}

_________________________________________________________________________________

Labels:

Comments

  1. UnknownAugust 30, 2017 at 10:04 PM

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

    ReplyDelete

Post a Comment

Popular posts from this blog

MonoLithic Vs Microservice Architecture | which Architecture should i choose ?

From last few years ,microservices are an accelerating trend . Indeed, microservices approach offers tangible benefits including an increase in scalability, flexibility, agility, and other significant advantages. Netflix, Google, Amazon, and other tech leaders have successfully switched from monolithic architecture to microservices. Meanwhile, many companies consider following this example as the most efficient way for business growth. On the contrary, the monolithic approach is a default model for creating a software application. Still, its trend is going down because building a monolithic application poses a number of challenges associated with handling a huge code base, adopting a new technology, scaling, deployment, implementing new changes and others. So is the monolithic approach outdated and should be left in the past? And is it worth shifting the whole application from a monolith to microservices ? Will developing a microservices application help you reach you...
Post a Comment
Read more

C Program to sort an array using insertion sort

I have seen couple of students who use swap in insertion sort to sort an array.Insertion sort is an example of exchange sort ,we don't swap two elements to sort an array ,instead of this we shift elements if ith element is greater than i+1th element to sort an array.It works on simple concept:- Store the ith element in temporary variable and shift element until you find the element smaller than this element towards 0 index position.Here is the C Program to find insertion sort:- _________________________________________________________________________________ #include <stdio.h> #include <string.h> main() {     int arrSize,i;    printf("Enter Size of array:");    scanf("%d",&arrSize);    int array[arrSize];    for(i=0;i<arrSize;i++){        scanf("%d",&array[i]);    }    int temp,j;    for(i=1;i<arrSize;i++){        temp...
3 comments
Read more

Sudoku using dancing link - Java implementation

Here is a algorithm which uses dancing link to solve algorithm X(exact cover) that solves upto 100*100 sudoku. Algorithm has been implemented using  JAVA and can be able to solve Sudoku of any difficulty level(easy,hard,very hard). Algorithm works as follows:- 1.) Algorithm first find out the number of possible elements in each cell , algorithm for this can be seen in the code. 2.) After this apply rule1 which says finds  that cell which has a single possible element , this works recursively until we find single possible element. 3.) After this apply rule2 which says if there is a number which can go into only one cell, then assign that number to that cell. 4.) Rule2 and rule1 run recursively. 5.) Still if we find possible number of elements in some cell then create a dancing link for sudoku puzzle , reduce the puzzle in to exact cover form and solve it using algorithm X in a efficient way.To make it efficient,first we implemented rule1 and rule2 ,firstly algorithm try...
Post a Comment
Read more