Skip to main content

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

}
_________________________________________________________________________________
Labels:

Comments

Post a Comment

Popular posts from this blog

Long-Polling vs WebSockets vs Server-Sent Events

Long-Polling vs WebSockets vs Server-Sent Events  Long-Polling, WebSockets, and Server-Sent Events are popular communication protocols between a client like a web browser and a web server. First, let’s start with understanding what a standard HTTP web request looks like. Following are a sequence of events for regular HTTP request: Client opens a connection and requests data from the server. The server calculates the response. The server sends the response back to the client on the opened request. HTTP Protocol Ajax Polling Polling is a standard technique used by the vast majority of AJAX applications. The basic idea is that the client repeatedly polls (or requests) a server for data. The client makes a request and waits for the server to respond with data. If no data is available, an empty response is returned. Client opens a connection and requests data from the server using regular HTTP. The requested webpage sends requests to...
Post a Comment
Read more

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

Face Detection model on Image/Webcam/Video using Machine Learning OpenCV

Face detection is a computer technology that is being applied for many different applications that require the identification of human faces in digital images or video. It can be regarded as a specific case of object-class detection, where the task is to find the locations and sizes of all objects in an image that belongs to a given class. The technology is able to detect frontal or near-frontal faces in a photo, regardless of orientation, lighting conditions or skin color . Not Face Recognition! It’s about Detection. Face recognition describes a biometric technology that goes way beyond recognizing when a human face is present. It actually attempts to establish whose face it is. In this article, I’m not going deep into recognizing. I’ll keep that for a future blog article and for the time being, I’m going to explain how to run a simple Face  Detection program using your WebCam with Python Or we can run simple program on image as well . We are dealing with below Cascade models for...
Post a Comment
Read more