Home » Technical Interview Questions » Array Interview Questions » Maximum Sum of Non Consecutive Elements

Maximum Sum of Non Consecutive Elements


Reading Time - 3 mins

In the given array, you need to find the maximum sum of non consecutive elements. You can not add immediate neighbor numbers. For example [1,3,5,6,7,8,] here 1, 3 are adjacent so we can’t add them and 6, 8 are not adjacent so we can add them.

Example

Input

4 10 8 -5 6 9 2

Output

21

Algorithm for finding Maximum Sum of Non Consecutive Elements

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

Explanation for finding Maximum Sum of Non Consecutive Elements

Input

6, 12, 10, 26, 20

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

READ  Minimum Index Sum of Two Lists

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 for finding Maximum Sum of Non Consecutive Elements

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int incl_sum = a[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 + a[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;
}
8
1 1 2 2 2 3 4 5 
11

Complexity Analysis

Time Complexity – O(N) where n is the size of the array. Here we traverse the whole array and find the answer.
Space Complexity – O(1) because we use some variables only which leads us to constant space complexity.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions