Maximum Sum of Non Consecutive Elements

Problem Statement

In the “Maximum Sum of Non Consecutive Elements” 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

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

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.

Implementation

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;
}

import static java.lang.Math.max;
import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        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); 
        System.out.println(max_sum);
    }
}

8
1 1 2 2 2 3 4 5 

11