ronith
10/31/2018 - 5:53 AM

Maximum sum such that no two elements are adjacent

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.

Maximum sum such that no two elements are adjacent.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/
#include <iostream>
using namespace std;

int main() {
    int n;
    cin>>n;
    int a[n];
    for (int i=0;i<n;i++)
        cin>> a[i];
    int inc=a[0], exc=0, ex;

    for (int i=1;i<n;i++) {
        ex= (inc>exc)?inc:exc;

        inc= exc + a[i];
        exc= ex;
    }
    inc>exc?cout<<inc:cout<<exc;
}