Friday, September 12, 2014

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.