Find the maximum sum such that numbers are not adjacent (consecutive)

In the given array, you need to find maximum sum of elements such that no two are adjacent (consecutive). You can not add immediate neighbour numbers. 

Adjacent: side by side

For example [1,3,5,6,7,8,] here 1, 3 are adjacent and 6, 8 are not adjacent.

Example

Given input array be,

Output is 4 + 8 + 9 = 21

ALGORITHM

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(1)

  1. Take two variables incl_sum and excl_sum such that they represent sum formed by including the element on which you are standing and sum formed by excluding that element respectively.
  2. Traverse the array
  3. Initialize incl_sum as the first element and excl_sum to be zero.
  4. For each element find the maximum of incl_sum and excl_sum.
  5. Incl_sum will be equal to the sum of present element and excl_sum as excl_sum was calculated till one less index than the current element.
  6. excl_sum will be simply the maximum found out at step 4.
  7. Finally after traversal answer will be maximum of incl_sum and excl_sum.

Algorithm Working Example

Input array

Applying algorithm on the given array,

inc = 6
exc = 0

Step 1

For i = 1 (current element is 12)
max_till_now = max(6,0) = 6
incl =  (excl + arr[i])  = 12
excl =  6

Step 2

For i = 2 (current element is 10)
max_till_now = max(12,6) = 12 
incl =  (excl + arr[i]) = 16
excl =  12

Step 3

For i = 3 (current element is 26)
max_till_now = max(16,12) = 16
incl = (excl + arr[i]) = 38
excl = 16

Step 4

For i = 4 (current element is 20)
max_till_now = max(38,16) = 38
incl = (excl + arr[i]) = 36
excl =  38
Finally answer is max(38,36) = 38.

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	  int arr[] = {4,10,8,-5,6,9,2}; //Array
      int N = sizeof(arr)/sizeof(arr[0]); //size of array
 		
 		int incl_sum = arr[0],excl_sum = 0; //include first element	 or exclude it
 		int max_sum;
 		for(int i=1;i<N;i++)
 		{
 			max_sum = max(incl_sum,excl_sum);
			incl_sum = excl_sum + arr[i]; // excluded sum is till one before the adjacent element	
			excl_sum = max_sum; // we will take the sum which is larger to obtain maximum sum
		}
		max_sum = ((incl_sum > excl_sum)? incl_sum : excl_sum); 
 		cout << max_sum;
 
 		return 0;
}
Try It

 


Next > < Prev
Scroll to Top