QUESTION

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. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).\n\nInput:\n\nThe first line of input contains an integer T denoting the number of test cases.\nThe first line of each test case is N,N is the size of array.\nThe second line of each test case contains N input C[i].\n\nOutput:\n\nPrint the maximum sum of a subsequence.\n\nConstraints:\n\n1 T 80\n1 N 100\n1 C[i] 500.

“TESTCASE_1”: “2\n6\n5 5 10 100 10 5\n4\n3 2 7 10\n###—###SEPERATOR—###—\n110\n13”, “TESTCASE_2”: “2\n6\n7 7 20 200 8 4\n4\n4 3 2 1\n###—###SEPERATOR—###—\n211\n6”, “TESTCASE_3”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<stdio.h>

/*Function to return max sum such that no two elements
 are adjacent */
int FindMaxSum(int arr[], int n)
{
  int incl = arr[0];
  int excl = 0;
  int excl_new;
  int i;

  for (i = 1; i < n; i++)
  {
     /* current max excluding i */
     excl_new = (incl > excl)? incl: excl;

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

   /* return max of incl and excl */
   return ((incl > excl)? incl : excl);
}

/* Driver program to test above function */
int main()
{
  int i,n,t;
  scanf("%d",&t);
  while(t--)
  {
  scanf("%d",&n);
  int arr[n];
  for(i=0;i<n;i++)
    scanf("%d",&arr[i]);
  
  printf("%d\n", FindMaxSum(arr, n));
  }
  return 0;
}