Friday, May 15, 2015

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.


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
  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.


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)

No comments:

Post a Comment