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

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 is given below.

/* C++ program to find the maximum sum such that no two elements in an array are adjacent */

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,k;
cin>>n;
cin>>k;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int dp[n][2];
dp[0][0]=a[0];
dp[0][1]=a[0];
for(int i=1;i<n;i++)
{
if(i<=k)
{
dp[i][0]=max(a[i],dp[i-1][0]);
}
else
{
dp[i][0]=max(dp[i-1][0],max(a[i],a[i]+dp[i-k-1][0]));
}
}
cout<<dp[n-1][0]<<endl;
return 0;
}

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