Question

Sequence a1,a2……an consists of nonnegative integers. We want to determine the largest sum of such subsequences that do not contain two consecutive elements of the original sequence (For example if a3 is a member of the subsequence, then a2 and a4 cannot be contained in the subsequence ). Give an O(n) running time algorithms for this problem.

Answer 1

Given sequence a1,a2.....an.
To find maximum sum of subsequence that do not contain two consecutive elements.
We will use Dynamic programming to solve given problem.

Algorithm:
Create an array DP[1...n] of size n that stores maximum sum of subsequence that do not contain two consecutive elements.
for i=1 to n
if(i==1) DP[i] = a[i];
if(i==2) DP[i] = maximum(DP[0],a[1]);
else DP[i] = maximum(DP[i-2]+a[i],DP[i-1]);

print DP[n] will give maximum sum of subsequence that do not contain two consecutive elements.
Time complexity = O(n)