Max Sum without Adjacents

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro