Hello Everyone,
Given an array of positive numbers, find the maximum sum of a subsequence with the constraint that no 2 numbers in the sequence should be adjacent in the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7).Answer the question in most efficient way.
Examples :
Input : arr[] = {5, 5, 10, 100, 10, 5}
Output : 110
Input : arr[] = {1, 2, 3}
Output : 4
Input : arr[] = {1, 20, 3}
Output : 20
Algorithm:
Loop for all elements in arr[] and maintain two sums incl and excl where incl = Max sum including the previous element and excl = Max sum excluding the previous element.
Max sum excluding the current element will be max(incl, excl) and max sum including the current element will be excl + current element (Note that only excl is considered because elements cannot be adjacent).
At the end of the loop return max of incl and excl.
Example:
arr[] = {5, 5, 10, 40, 50, 35}
incl = 5
excl = 0
For i = 1 (current element is 5)
incl = (excl + arr[i]) = 5
excl = max(5, 0) = 5
For i = 2 (current element is 10)
incl = (excl + arr[i]) = 15
excl = max(5, 5) = 5
For i = 3 (current element is 40)
incl = (excl + arr[i]) = 45
excl = max(5, 15) = 15
For i = 4 (current element is 50)
incl = (excl + arr[i]) = 65
excl = max(45, 15) = 45
For i = 5 (current element is 35)
incl = (excl + arr[i]) = 80
excl = max(65, 45) = 65
And 35 is the last element. So, answer is max(incl, excl) = 80
Implementation:
//c++ program for the above approach
#include <bits/stdc++.h>
using
namespace
std;
/*Function to return max sum such that no two elements
are adjacent */
int
FindMaxSum(vector<
int
> arr,
int
n)
{
int
incl = arr[0];
int
excl = 0;
int
excl_new;
int
i;
for
(i = 1; i < n; i++)
{
/* current max excluding i */
excl_new = (incl > excl) ? incl : excl;
/* current max including i */
incl = excl + arr[i];
excl = excl_new;
}
/* return max of incl and excl */
return
((incl > excl) ? incl : excl);
}
// Driver program to test above functions
int
main()
{
vector<
int
> arr = {5, 5, 10, 100, 10, 5};
cout<<FindMaxSum(arr, arr.size());
}
Output:
110
Time Complexity: O(n)