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
 
Example:
Input:

2  3  1  5

Output:

Maximum sum would be 3+5=8.

Algorithm:

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’:

        -old_inc=inc;

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

  {

    old_inc=inc;

    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:

O(n)

Go to top