undefined | Better HN

0 pointscolorint9y ago0 comments

Well, the answer for an array of all negative numbers is to choose no elements, or if you must choose one, to choose the maximum single element. But presumably you solve it with the normal algorithm but with one level of look-behind. Something like,

  function maxsum(arr)
    local max2 = function(a, b) if a > b then return a else return b end end
    local max3 =
      function(a, b, c)
        if a > b and a > c then return a
        elseif b > c then return b
        else return c end end
    local best = 0
    local best_here = 0
    local i = 2
    while i <= table.maxn(arr) do
      best_here = max3(0, best_here + arr[i], best_here + arr[i-1])
      best = max2(best, best_here)
      if arr[i] > arr[i-1] then i = i + 2 else i = i + 1 end
    end
    return best
  end

  print(maxsum{1, -1, 2, -2, 3, -3, -4, 4, -5})

Assuming this algorithm is correct (it worked for my couple of test cases), the main trickiness is that you have to skip two elements if you choose the current one, to make sure that you don't double-choose.

0 comments

2 comments · 1 top-level

josephorjoe9y ago· 1 in thread

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

colorintOP9y ago

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.

j / k navigate · click thread line to collapse

function maxsum(arr) local max2 = function(a, b) if a > b then return a else return b end end local max3 = function(a, b, c) if a > b and a > c then return a elseif b > c then return b else return c end end local best = 0 local best_here = 0 local i = 2 while i <= table.maxn(arr) do best_here = max3(0, best_here + arr[i], best_here + arr[i-1]) best = max2(best, best_here) if arr[i] > arr[i-1] then i = i + 2 else i = i + 1 end end return best end print(maxsum{1, -1, 2, -2, 3, -3, -4, 4, -5})