Explore
Placement Prep

Edit

Edit

# Find the maximum sum such that no two elements in the array are adjacent

Published on 11 Mar 2020

Program to find the maximum sum such that no two elements in the array are adjacent is discussed here.

Sample Input:

arr = {-9, 63, -100, 25, 89, -96, 63, 45, 78 }

Sample Output:

293

Explanation:

63 +89 +63 + 78 = 293

## Algorithm to find the maximum sum such that no two elements in an array are adjacent

• Input the number of elements of the array.
• Input the array elements.
• For all possible combinations, find the sum and compare it with the previous sum and update the maximum sum.
• The solution to this problem is approached using a dynamic programming technique.

## Program to find the maximum sum such that no two elements in an array are adjacent

C++

Output
Input -
9 1
3 4 -2 1 -2 4 6 -3 5
Output-
13 5

Test Case 1

Input

9 1

3 4 -2 1 -2 4 6 -3 5

Output

13 5

Test Case 2

Input

9 1

-9 63 -100 25 89 -96 63 45 78

Output

230 -196

Test Case 3

Input

10 3

45 -96 30 87 -9 3 -10 8 6 -9

Output

95 -106

Test Case 4

Input

10 1

45 -96 30 87 -9 3 -10 8 6 -9

Output

143 -124

Test Case 5

Input

10 2

9 6 3 -7 -5 1 9 -6 -7 3

Output

21 -14

Recommended Programs