Sunday, 29 January 2017

Maximum sum non-adjacent elements Recursive Solution: C program

Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array.

#include<stdio.h>

/*Function to return max sum such that no two elements are adjacent */
int FindMaxSum(int *a, int index, int n)
{
  static int incl = a[0];
  static int excl = 0;
  int temp;
  if(index == n)
   return incl;
   else
   {
        temp=incl;
    if(incl<(excl+a[index]))
    incl=excl+a[index];
    excl = temp;
FindMaxSum(a,index+1,n);
   }
 
}
int main()
{
  int a[] = {5, 5, 10, 100, 10, 5};
  int size=sizeof(a)/sizeof(a[0]);
  printf("\nMaximum sum of non- adjacent elements= %d \n", FindMaxSum(a,1, size));
  return 0;
}

No comments:

Post a Comment