Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




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





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises