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