Maximum sum such that no two elements are adjacent

Question: Given an array all of whose elements are 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.

Using Dynamic Programming : you have to maintain an array maxsum[] such that maxsum[i] has the maximum sum till the ith element. and

maxsum[i]=max(maxsum[i-2],maxsum[i-3])+arr[i];
and the catch is that we have to include either the 1st element or the 2nd element in the maxsum
so
maxsum[0]=arr[0];
maxsum[1]=arr[1];
maxsum[2]=arr[0]+arr[2];
now apply the recursive structure from the 4th element onwards.

This would take O(n) time and then find the maximum element of maxsum. O(n).