def rob(x):
rewards = [-1] * len(x)
tracks = [-1] * len(x)
rewards[0] = x[0]; rewards[1] = x[1]
tracks[0] = 0; tracks[1] = 1
best_end = 0 if rewards[0] > rewards[1] else 1
for i in range(2, len(x)):
for j in range(0,i-1):
if rewards[j] + x[i] > rewards[i]:
rewards[i] = rewards[j] + x[i]
tracks[i] = j
if rewards[i] > rewards[best_end]:
best_end = i
final_track = [best_end]
final_reward = rewards[best_end]
while tracks[best_end] != best_end:
best_end = tracks[best_end]
final_track.append(best_end)
return final_reward, list(reversed(final_track))
print(rob([1, 3, 7, 3, 11, 9, 2, 10]))
print(rob([1, 3, 7, 3, 2, 9, 10, 1]))
print(rob([1, 2, 3]))
ZGVmIHJvYih4KToKICAgIHJld2FyZHMgPSBbLTFdICogbGVuKHgpCiAgICB0cmFja3MgPSBbLTFdICogbGVuKHgpCiAgICByZXdhcmRzWzBdID0geFswXTsgcmV3YXJkc1sxXSA9IHhbMV0KICAgIHRyYWNrc1swXSA9IDA7IHRyYWNrc1sxXSA9IDEKICAgIGJlc3RfZW5kID0gMCBpZiByZXdhcmRzWzBdID4gcmV3YXJkc1sxXSBlbHNlIDEKICAgIGZvciBpIGluIHJhbmdlKDIsIGxlbih4KSk6CiAgICAgICAgZm9yIGogaW4gcmFuZ2UoMCxpLTEpOgogICAgICAgICAgICBpZiByZXdhcmRzW2pdICsgeFtpXSA+IHJld2FyZHNbaV06CiAgICAgICAgICAgICAgICByZXdhcmRzW2ldID0gcmV3YXJkc1tqXSArIHhbaV0KICAgICAgICAgICAgICAgIHRyYWNrc1tpXSA9IGoKICAgICAgICBpZiByZXdhcmRzW2ldID4gcmV3YXJkc1tiZXN0X2VuZF06CiAgICAgICAgICAgIGJlc3RfZW5kID0gaQogICAgZmluYWxfdHJhY2sgPSBbYmVzdF9lbmRdCiAgICBmaW5hbF9yZXdhcmQgPSByZXdhcmRzW2Jlc3RfZW5kXQogICAgd2hpbGUgdHJhY2tzW2Jlc3RfZW5kXSAhPSBiZXN0X2VuZDoKICAgICAgICBiZXN0X2VuZCA9IHRyYWNrc1tiZXN0X2VuZF0KICAgICAgICBmaW5hbF90cmFjay5hcHBlbmQoYmVzdF9lbmQpCiAgICByZXR1cm4gZmluYWxfcmV3YXJkLCBsaXN0KHJldmVyc2VkKGZpbmFsX3RyYWNrKSkKCnByaW50KHJvYihbMSwgMywgNywgMywgMTEsIDksIDIsIDEwXSkpCnByaW50KHJvYihbMSwgMywgNywgMywgMiwgOSwgMTAsIDFdKSkKcHJpbnQocm9iKFsxLCAyLCAzXSkpCg==
(29, [0, 2, 4, 7])
(20, [0, 2, 4, 6])
(4, [0, 2])