codepad

Language:

/**
 ******************************************************************************
 *
 * Given an array all of whose elements are 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. For example,
 *
 * i) 3 2 7 10 should return 13 (sum of 3 and 10)
 * ii) 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)
 *
  *
 ******************************************************************************
 */
#include <stdio.h>
#define max(a,b)  ((a)>(b))?(a):(b)

void PrintArray(int buf[],size_t cnt)
 {
   size_t i;
   static int c = 1;
   printf("Array %d: ",c++);
   for(i = 0; i<cnt; i++)
     {
      printf("%d",buf[i]);
      if(i+1 != cnt)printf("%s",",");
     }
   putchar('\n');
 }

int MaxNoncontSum(int buf[],size_t cnt)
 {
     int incl = 0,    // max sequence including the previous item
         excl = 0,   // max sequence excluding the previous item
         excl_new = 0;

size_t i;

for(i = 0; i<cnt; i++)
       {
         excl_new = max(incl,excl); // current max excluding i

incl = excl + buf[i]; // current max including i
         excl = excl_new;
       }

return max(incl,excl);
 }

int main (void)
{
    int array1[] = { 3, 2, 7, 10 };
    int array2[] = { 3, 2, 5, 10, 7 };
    int array3[] = { 3, 7, 2, 10, 9, 1 };

PrintArray(array1, sizeof(array1)/sizeof(int));
    printf("%s%d\n\n","Reqd Sum: ",MaxNoncontSum(array1, sizeof(array1)/sizeof(int)));

PrintArray(array2, sizeof(array2)/sizeof(int));
    printf("%s%d\n\n","Reqd Sum: ",MaxNoncontSum(array2, sizeof(array2)/sizeof(int)));

PrintArray(array3, sizeof(array3)/sizeof(int));
    printf("%s%d\n\n","Reqd Sum: ",MaxNoncontSum(array3, sizeof(array3)/sizeof(int)));

return(0);
}

Private [?]

Run code