Given is a path graph with weights on the nodes. Find an independent set of maximum weight in this path graph, i.e. find a subset consisting of mutually non-adjacent nodes where the sum of the weights on the nodes is as large as possible.

Design and implement an algorithm for this problem, using dynamic programming.

Assignment

Write a Python function WISPath(path:list) that takes a path as parameter, and returns the indices of the nodes in a maximum independent set in the path graph.

Example

>>> WISPath([1, 4, 5, 4, 2, 8, 1, 5, 2, 3, 4, 3, 10, 2])
[1, 3, 5, 7, 10, 12]