What is the best answer for finding the maximum sum possible in an array
algorithm, arrays, c
Solution
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.
Problem
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.