Description: We have to find the maximum sum of elements in an array containing positive numbers such that no 2 adjacent elements are included.

If video does not load, Click here

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)

Implementation using C:

/*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[0];

  int exc = 0;

  int old_inc;

  int i;

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


Time Complexity:


Go to top