What is the best answer for finding the maximum sum possible in an array [closed]

Question

The question is :

Find the maximum sum possible in an array of positive integers by selecting the elements in such a way that no two elements are next to each other.

there is an answer like this : but what is the best answer for this question

Let's denote the array by "t" and index it from 0. Let f be a function so that f(k)=the maximal sum in the [0..k] subarray with the conditions of the problem. Now use dynamic programming:

f(0) = t[0]
f(1) = max{ t[0], t[1] }
f(k) = max{ f(k-2) + t[k], f(k-1) } if k >= 2

If the array has n elements we need f(n-1).

Thanks in advance.

Answer 1

Solution you proposed is good one.

Similar approach (page 7 here):

Let m[i] be the maximum sum of any subarray that ends at the element a[i].Then m[i] is simply max(a[i], m[i-1]+a[i]).

This is O(n).

and you cant get anything below O(n) as you have to visit every item of the array atleast once to compute the result.

Answer 2

Well, I think this is already the best answer.
Since you need O(n) to read in the data.
an O(n) algorithm is the fastest in the big-O notation.