If by half the array you mean your solution must include either the first or second, and either the last or second-to-last, then the problem seems a lot simpler. This ought to work:
function maxsum(arr)
local max = function(a, b) if a > b then return a else return b end end
local best = {arr[1], arr[2]}
for i = 3, table.maxn(arr) do
best[i] = max(arr[i] + best[i-1], arr[i] + best[i-2])
end
return max(best[table.maxn(best)], best[table.maxn(best)-1])
end
print(maxsum{-1, -2, -3, -4, -5, -6})
This prints -9, though it's not set up to track which numbers it used. (It wouldn't be hard to modify it to make it do so.) Note that Lua uses one-indexing.
Comments
My understanding of the challenge (which could have been wrong...) was that you had to use at least one half of the array (every other number).
So if the array was [-1, -2, -3, -4, -5, -6], the 'max sum' would be -9 ([-1, -3, -5]).
I can't think of a non-brute force solution for an extended sequence of negative numbers...
If by half the array you mean your solution must include either the first or second, and either the last or second-to-last, then the problem seems a lot simpler. This ought to work:
This prints -9, though it's not set up to track which numbers it used. (It wouldn't be hard to modify it to make it do so.) Note that Lua uses one-indexing.