Problem Statement:
You are given an array, you need to find the maximum sum of subsequence where no 2 numbers in the sequence are adjacent.
So {3, 4, 5, 6} The max is 10 {6, 4}.
Solution
The solution is very simple.
We take 2 variables: incl = what will have Max sum including the previous element. excl = It will have Max sum excluding the previous element. The formula here will be: incl = excl + arr[i] excl = max(incl, excl)
Example:
arr[] = {5, 5, 10, 40, 50, 35} Pass 0: incl = 5 excl = 0 Pass 1: For i = 1 arr[1] = 5 incl = (excl + arr[i]) = 5 excl = max(5, 0) = 5 Pass 2: For i = 2 arr[2] = 10 incl = (excl + arr[i]) = 15 excl = max(5, 5) = 5 Pass 3: For i = 3 arr[3] = 40 incl = (excl + arr[i]) = 45 excl = max(5, 15) = 15 Pass 4: For i = 4 arr[4] = 50 incl = (excl + arr[i]) = 65 excl = max(45, 15) = 45 Pass 5: For i = 5 arr[5] = 35 incl = (excl + arr[i]) = 80 excl = max(65, 45) = 65 Answer = 80
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; int get_max_sum(int arr[], int n) { int incl = arr[0]; int excl = 0; int excl_new; int i; for (i = 1; i < n; i++) { excl_new = (incl > excl)? incl: excl; incl = excl + arr[i]; excl = excl_new; } return ((incl > excl)? incl : excl); } int main() { int arr[] = {5, 5, 10, 50, 10, 5}; int n = sizeof(arr) / sizeof(arr[0]); cout<<"The Max sum is = "<< get_max_sum(arr, n)<<endl; return 0; }
Output:
The Max sum is = 60