Description: We have to find the maximum sum of elements in an array containing positive numbers such that no 2 adjacent elements are included.
2 3 1 5
Maximum sum would be 3+5=8.
1.Initiate variable ‘exc’(max sum excluding) to 0 and ‘inc’(maximum sum including) to the first element in the array.
2.Iterate through the string starting from the 2nd element(index 1) using the variable ‘i’:
-inc= exc+ arr[i];
-exc= max(old_inc, exc);
3. Answer: max(inc, exc)
/*The following function returns the maximum sum of non-adjacent elements in an array.*/
int max_non_adjacent_sum(int arr, int n)
int inc = arr;
int exc = 0;
for (i = 1; i < n; i++)
inc=exc+arr[i]; /*include current element*/
exc=((old_inc>exc)?old_inc:exc); /*exclude current element*/
/* return max of inc and exc */
return ((inc > exc)? inc : exc);