Posts

Showing posts from August, 2014

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;          …

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…

Quick Sort algorithm to select random/middle/first/last element as a pivot

Below i have attached quick sort algorithm that can select pivot element position from the user for the first time and sort the array with  nlogn complexity.
Approx. in all the books ,algorithm shows to select  either first or last element as a pivot.This algorithm is able to select pivot position from user and sort the array elements accordingly.
Lets take an example:
95 5 1 3 7
try a quick sort dry run of this array elements on pen and paper,here 1 is a pivot element:-
1st pass:-1 5 95 3 7   (pivot element 1 is in final position)
2nd pass:-1 3 5 95 7  (now pivot element 5 is in final position)
3rd pass:-1 3 5 7 95   (pivot element 95 is in final position)

Just with the slight modification in the main & quick sort function , you can able to select middle element as a pivot element.To make a middle element as a pivot element,you only need to do three changes :
1.)Remove below two lines in the main function
   printf("Enter pivot element position===>\n");
   scanf(&qu…