Table of Contents

## 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

- 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.
- Traverse the array
- Initialize incl_sum as the first element and excl_sum to be zero.
- For each element find the maximum of incl_sum and excl_sum.
- 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.
- excl_sum will be simply the maximum found out at step 4.
- 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; }

### Java Program for finding Maximum Sum of Non Consecutive Elements

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

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