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