Maximum sum such that no two elements are adjacent

We are given an array of positive integres, and we need to find the sum of any subsequence in which any none of the any 2  element is adjacet element in the given array.

In other words, we need to come up with a sub sequence of the given array, whose sum is highest and none of 2 elements are adjacent in given array.

Let's take an example.

Given array

1 2 3 4 5

Here 1 and 2 are adjecent, similarly, 2 and 3 are adjacent. 

So, our answer would be 1 + 3 + 5 = 8. See we are not taking any element which are adjacent in array.

Another subsequnce with no adjacent elements would have been, 2, 4 but its total sum would be lesser so, that's not required answer.

I hope you have understood the problem clearly. Now, let's try to build an algorithm for it.

Solution

We'll loop over the array keeping 2 sums. We'll call them inclusive and exclusive. Why did we choose this name ?

Inclusive - Max sum including the previous element

Exlusive - Max sum excluding the previous element.

So, Inclusive can be given by, Exclusive + current element

and, Exclusive will be max(Inclusive, Exclusive)

Implementation

#include<bits/stdc++.h>
using namespace std;
int FindMaxSum(int arr[],int n)
{
	int incl=arr[0]; //we are taking this as arr[0] because we are including arr[0] value in sum
	int excl=0;  //since we have no other after we exclude arr[0] so thats why we are taking excl =0
	for(int i=1;i<n;i++)
	{
		int temp=incl;   
		incl=max(temp,arr[i]+excl); // suppose at any point of time we are at arr[1] so now temp will contain
		                            // the value of arr[0] since we can not use adjacent value so for that we are
		                            // taking maximum of previous value of arr[1] i.e arr[0] and in this case it is 
		                            // temp  and if we are including arr[1] value then we can use excl value that 
		                            // is value before arr[0] in this case it is 0 because if we add that then it is not 
		                            // its adjacent value.
		excl=temp;                  // excl will go over all value starting from arr[0] to arr[n-2]
	}
	return incl;
}
int main()
{
	int arr[] = {1, 2, 3}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	cout<<FindMaxSum(arr, n); 
	return 0; 
}

4