Searching and Sorting: Maximum sum such that no two elements are adjacent

Problem Statement:

You are given an array, you need to find the maximum sum of subsequence where no 2 numbers in the sequence are adjacent.

So {3, 4, 5, 6} The max is 10 {6, 4}.

Solution

The solution is very simple.

We take 2 variables:
incl = what will have Max sum including the previous element.

excl = It will have Max sum excluding the previous element.

The formula here will be:

incl = excl + arr[i]
excl = max(incl, excl)

Example:

arr[] = {5,  5, 10, 40, 50, 35}

Pass 0:
  incl = 5 
  excl = 0

Pass 1:
  For i = 1 arr[1] = 5
  incl =  (excl + arr[i])  = 5
  excl =  max(5, 0) = 5

Pass 2:
  For i = 2 arr[2] = 10
  incl =  (excl + arr[i]) = 15
  excl =  max(5, 5) = 5

Pass 3:
  For i = 3 arr[3] = 40
  incl = (excl + arr[i]) = 45
  excl = max(5, 15) = 15

Pass 4:
  For i = 4 arr[4] = 50
  incl = (excl + arr[i]) = 65
  excl =  max(45, 15) = 45

Pass 5:
  For i = 5 arr[5] = 35
  incl =  (excl + arr[i]) = 80
  excl =  max(65, 45) = 65

Answer = 80

Solution in C++

#include <vector>    
#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <unordered_map>
#include <vector>
#include <sstream> 

using namespace std;


int get_max_sum(int arr[], int n) 
{ 
  int incl = arr[0]; 
  int excl = 0; 
  int excl_new; 
  int i; 
  
  for (i = 1; i < n; i++) 
  { 
     excl_new = (incl > excl)? incl: excl; 
  
     incl = excl + arr[i]; 
     excl = excl_new; 
  } 
  
   return ((incl > excl)? incl : excl); 
} 
  
int main() 
{ 
  int arr[] = {5, 5, 10, 50, 10, 5}; 
  int n = sizeof(arr) / sizeof(arr[0]); 
  cout<<"The Max sum is = "<< get_max_sum(arr, n)<<endl; 
  return 0; 
}

Output:

The Max sum is = 60