fork download
  1. def rob(x):
  2. rewards = [-1] * len(x)
  3. tracks = [-1] * len(x)
  4. rewards[0] = x[0]; rewards[1] = x[1]
  5. tracks[0] = 0; tracks[1] = 1
  6. best_end = 0 if rewards[0] > rewards[1] else 1
  7. for i in range(2, len(x)):
  8. for j in range(0,i-1):
  9. if rewards[j] + x[i] > rewards[i]:
  10. rewards[i] = rewards[j] + x[i]
  11. tracks[i] = j
  12. if rewards[i] > rewards[best_end]:
  13. best_end = i
  14. final_track = [best_end]
  15. final_reward = rewards[best_end]
  16. while tracks[best_end] != best_end:
  17. best_end = tracks[best_end]
  18. final_track.append(best_end)
  19. return final_reward, list(reversed(final_track))
  20.  
  21. print(rob([1, 3, 7, 3, 11, 9, 2, 10]))
  22. print(rob([1, 3, 7, 3, 2, 9, 10, 1]))
  23. print(rob([1, 2, 3]))
  24.  
Success #stdin #stdout 0.04s 9316KB
stdin
Standard input is empty
stdout
(29, [0, 2, 4, 7])
(20, [0, 2, 4, 6])
(4, [0, 2])