## In the given array, you need to find maximum sum of elements such that no two are adjacent (consecutive). You can not add immediate neighbour numbers.

Adjacent: side by side

For example [1,3,5,6,7,8,] here 1, 3 are adjacent and 6, 8 are not adjacent.

### Example

Given input array be,

Output is 4 + 8 + 9 = 21

## ALGORITHM

**TIME COMPLEXITY â€“ O(N)**

**SPACE COMPLEXITY â€“ O(1)**

- Take two variables incl_sum and excl_sum such that they represent sum formed by including the element on which you are standing and sum formed by excluding that element respectively.
- Traverse the array
- Initialize incl_sum as the first element and excl_sum to be zero.
- For each element find the maximum of incl_sum and excl_sum.
- Incl_sum will be equal to the sum of present element and excl_sum as excl_sum was calculated till one less index than the current element.
- excl_sum will be simply the maximum found out at step 4.
- Finally after traversal answer will be maximum of incl_sum and excl_sum.

**Algorithm Working Example**

**Input array**

Applying algorithm on the given array,

inc = 6

exc = 0

**Step 1**

For i = 1 (current element is 12)

max_till_now = max(6,0) = 6

incl =Â (excl + arr[i])Â = 12

excl =Â 6

**Step 2**

For i = 2 (current element is 10)

max_till_now = max(12,6) = 12

incl =Â (excl + arr[i]) = 16

excl =Â 12

**Step 3**

For i = 3 (current element is 26)

max_till_now = max(16,12) = 16

incl = (excl + arr[i]) = 38

excl = 16

**Step 4**

For i = 4 (current element is 20)

max_till_now = max(38,16) = 38

incl = (excl + arr[i]) = 36

excl =Â 38

Finally answer is max(38,36) = 38.

## C++ Program

```
#include <bits/stdc++.h>
using namespace std;
int main()
{
int arr[] = {4,10,8,-5,6,9,2}; //Array
int N = sizeof(arr)/sizeof(arr[0]); //size of array
int incl_sum = arr[0],excl_sum = 0; //include first element or exclude it
int max_sum;
for(int i=1;i<N;i++)
{
max_sum = max(incl_sum,excl_sum);
incl_sum = excl_sum + arr[i]; // excluded sum is till one before the adjacent element
excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
}
max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum);
cout << max_sum;
return 0;
}
```