[GeeksforGeeks] Maximum sum such that no two elements are adjacent

Maximum sum such that no two elements are adjacent

Question: Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.

Analysis:  
DP comes to the picture. A similar problem would be 'Maximum sum of consecutive elements in a array', the difference is that when scans an element A[i], current maximum sum is chosen between previous max sum includes A[i-1] and a different max sum that does NOT include A[i-1].

Solution: 

int max(int a, int b)
{
return (a > b) ? a : b;
}

int maxSum(int *a, int n)
{
if(n <= 0)
     return 0;

     // include_sum is current max sum that includes a[i]
int include_sum = a[0];

     // exclude_sum is current max sum that does NOT include a[i]
int exclude_sum = 0;

int max_val = max(include_sum,  exclude_sum);

int i;
for(i = 1; i < n; i++)
{
                // Add two temp variables for readiness
               int prev_inc = include_sum;
                int prev_excl = exclude_sum;

                // current max sum that includes a[i]
include_sum = max(prev_excl + a[i], a[i]);  

               // current max sum that does NOT include a[i]
exclude_sum = max(prev_inc,  prev_excl);

  // max sum is chosen from above
max_val = max(max_val, max(include_sum, exclude_sum));
}

return max_val;

}