Synopsys Question: Find the maximum sum in an array with no two elements are adjacent

Problem: Find the maximum sum in an array such that no two elements are adjacent.

Solution: 

Maintain two sums for each element of the given array:

1. sum1 = Max sum including the previous element
2. sum2 = Max sum excluding the previous element

Now:

1. Max sum excluding the current element = max(sum1, sum2)
2. Max sum including the current element = arr[i] + sum2

At the end max of the sum1 and sum2 will be our resultant value.

Implementation:

int maxSumWithoutAdjacentElem(int *arr, int len)
{
if(arr == NULL || len == 0)
return -1; //Error value

int sumIncludingCurr = arr[0], sumExcludingCurr = 0;

for(int i = 1; i < len; ++i)
{
int tempExcludingSum = max(sumIncludingCurr, sumExcludingCurr);
sumIncludingCurr = sumExcludingCurr + arr[i];
sumExcludingCurr = tempExcludingSum;
}

return max(sumIncludingCurr, sumExcludingCurr);
}

Complexity: O(n)