Since you are taking an algorithms class you decided to create a fun candy hunting game for Halloween. You set up a maze with one way streets that can be thought of as a directed graph G (V,E). Each node v in the maze has w(v) amount of candy located at v . Each of your friends, starting at a given node s, has to figure out the maximum amount of candy they can collect. Note that candy at node v can be collected only once even if the node v is visited again on the way to some other place. Your friends complain that they can collect more candy if they get to choose the starting node. You agree to their their request and ask them to maximize the amount of candy they can collect starting at any node they choose. Before you ask your friends to solve the game you need to know how to do it yourself! Describe efficient algorithms for both variants. Ideally your algorithm should run in linear time. Hint: Consider what happens if G is strongly connected and if it is a DAG. No proof necessary if you use reductions to standard algorithms via graph transformations and simple steps. Otherwise you need to prove the correctness. Since you are taking an algorithms class you decided to create a fun candy hunting game for Halloween. You set up a maze with one way streets that can be thought of as a directed graph G (V,E). Each node v in the maze has w(v) amount of candy located at v . Each of your friends, starting at a given node s, has to figure out the maximum amount of candy they can collect. Note that candy at node v can be collected only once even if the node v is visited again on the way to some other place. Your friends complain that they can collect more candy if they get to choose the starting node. You agree to their their request and ask them to maximize the amount of candy they can collect starting at any node they choose. Before you ask your friends to solve the game you need to know how to do it yourself! Describe efficient algorithms for both variants. Ideally your algorithm should run in linear time. Hint: Consider what happens if G is strongly connected and if it is a DAG. No proof necessary if you use reductions to standard algorithms via graph transformations and simple steps. Otherwise you need to prove the correctness