Max weight independent set of a path graph

max_weight_independent_set

def max_weights(a):

	weights = [0] * (len(a) + 2)

	for i, v in enumerate(a):
		j = i + 2
		with_v = weights[j-2] + v
		without_v = weights[j-1]
		weights[j] = max(with_v, without_v)

	return weights


def max_weight_independent_set(a):
	weights = max_weights(a)
	elements = []
	j = len(weights) - 1
	while j > 1:
		i = j - 2
		if weights[j] - weights[j-2] == a[i]:
			elements.append(a[i])
			j -= 2
		else:
			j -= 1
	elements.reverse()		
	return elements