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
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.