As your reward for saving the Kingdom of Bigfunnia from the evil monster Exponential Asymptotic, the king has given you the opportunity to earn a big reward. Behind the castle there is a maze, and along each corridor of the maze there is a bag of gold coins. The amount of gold in each bag varies. You will be given the opportunity to walk through the maze, picking up bags of gold. You may enter only through the door marked ENTER and exit through the door marked EXIT. (These are distinct doors.) While in the maze you may not retrace your steps. Each corridor of the maze has an arrow painted on the wall. You may only go down the corridor in the direction of the arrow. There is no way to traverse a loop in the maze. You will receive a map of the maze, including the amount of gold in and the direction of each corridor. Describe and analyze an efficient algorithm to help you pick up the most gold in this maze while traversing a path from the start to the finish.

NOTE: PLEASE DO NOT WRITE REAL CODE. PSEUDOCODE IS FINE. Also, please prove the running time of your algorithm.