Daily Coding Problem: Problem #9 [Hard]

test.rb

# Given a list of integers, write a function that returns the largest sum of non-adjacent numbers. Numbers can be 0 or negative.

# For example, [2, 4, 6, 2, 5] should return 13, since we pick 2, 6, and 5. [5, 1, 1, 5] should return 10, since we pick 5 and 5.

# Follow-up: Can you do this in O(N) time and constant space?

def find_next(array, acc, idx, path)
  acc = 0 if acc.nil?
  return [acc, path] if array[idx].nil?
  return [acc, path] if idx >= array.length - 2 && idx > 1

  # check what are the values 2, 3 and 4 steps ahead
  step2 = array[idx + 2] ? array[idx + 2] : 0
  step3 = array[idx + 3] ? array[idx + 3] : 0
  step4 = array[idx + 4] ? array[idx + 4] : 0
  
  if step2 + step4 > step3
#     taking step 2 and 4 is better
    acc += step2 + step4
    path << step2
    path << step4
    return find_next(array, acc, idx + 4, path)
  else
    #     taking step 3 is better
    acc += step3
    path << step3
    return find_next(array, acc, idx + 3, path)
  end
end

# start script from index 0 and index 1
# compare results ang give best one
def run(array)
  sumA, pathA = find_next(array, array[0], 0, [array[0]])
  sumB, pathB = find_next(array, array[1], 1, [array[1]])
  p "sumA, pathA: #{sumA} #{pathA}"
  p "sumB, pBthB: #{sumB} #{pathB}"
  if sumA > sumB 
    [sumA, pathA]
  else 
    [sumB, pathB]
  end
end

run([2,4,6,2,5])
run([5,1,1,5])
run([1,5,1,5])
run([2,4,6,3])
run([1,2,1,2,3,1,2])
run([1,2,1,2,3,9,2])
run([1,3,1,2,4,1,2])
run([1,3,3,2,4,1,2])
run([1])
run([1,3])