arrays - Maximum sum of non consecutive elements

Question

Given an array of positive integers, what's the most efficient algorithm to find non-consecutive elements from this array which, when added together, produce the maximum sum?

Answer 1

Dynamic programming? Given an array A[0..n], let M(i) be the optimal solution using the elements with indices 0..i. Then M(-1) = 0 (used in the recurrence), M(0) = A[0], and M(i) = max(M(i - 1), M(i - 2) + A[i]) for i = 1, ..., n. M(n) is the solution we want. This is O(n). You can use another array to store which choice is made for each subproblem, and so recover the actual elements chosen.