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

For {3,-2, 1, 0, -4, 2} it is

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.

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.