Close

Maximum sum of a subsequence with no contiguous elements

Given an array of positive and negative numbers, find the maximum sum of any sub sequence such that no two elements are contiguous.

For example consider the array {3,-2, 1, 7}, maximum sum is 10 for {3,7}
For {3,-2, 1, 0, -4, 2} it is 6 for {3,1,2}

This problem can be efficiently solved in O(n) time using dynamic programming technique.

The approach here is simple. We take an auxiliary array with the same size as input. 

The entries in this array are calculated as follows.

Aux[i] = Aux[i] if i = 0
       = Max( Aux[0], Aux[1] ) if i = 1
       = Max( Aux[i-2]+arr[i], Aux[i-1] ) otherwise

Here is the C++ implementation of the above approach. It takes O(n) time and O(n) space.



#include <iostream>
#include <vector>
using namespace std;
long getMaxSumNoContiguous(vector<int> arr)
{
//Base cases
if( arr.size() == 0 )
return 0;
else if( arr.size() == 1 )
return arr[0];
vector<long> aux(arr.size());//auxilarry array
int i;
aux[0] = arr[0];
aux[1] = max( arr[0], arr[1] );
for( i = 2; i < arr.size(); i++ )
{
aux[i] = max(arr[i], max(aux[i-1], aux[i-2]+arr[i]));
}
return aux[arr.size()-1];
}
void Test1()
{
int arr[] = {1};
vector<int> input( arr, arr+1);
cout << getMaxSumNoContiguous(input) << endl;
}
void Test2()
{
int arr[] = {3,-6};
vector<int> input( arr, arr+2);
cout << getMaxSumNoContiguous(input) << endl;
}
void Test3()
{
int arr[] = {3,-2, 1, 7};
vector<int> input( arr, arr+4);
cout << getMaxSumNoContiguous(input) << endl;
}
void Test4()
{
int arr[] = {3,-2, 1, 0, -4, 2};
vector<int> input( arr, arr+6);
cout << getMaxSumNoContiguous(input) << endl;
}
void Test()
{
Test1();
Test2();
Test3();
Test4();
}
int main()
{
Test();
return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *