A part of doing business internationally involves the trading of different currencies, and the markets that facilitate such trades can fluctuate during a trading day in ways that create profit opportunities. For example, at a given moment during a trading day, 1 U.S. dollar might be worth 0.98 Canadian dollar, 1 Canadian dollar might be worth 0.81 euros, and 1 euro might be worth 1.32 U.S. dollars. Sometimes, as in this example, it is possible for us to perform a cyclic sequence of currency exchanges, all at the same time, and end up with more money than we started with, which is an action known as currency arbitrage. For instance, with the above exchange rates, we could perform a cyclic sequence of trades from U.S. dollars, to Canadian dollars, to euros, and back to U.S. dollars, which could turn $1,000,000 into $1,047,816, ignoring the commissions and other overhead costs for performing currency exchanges (which we will indeed be ignoring in this exercise). Suppose you are given a complete directed graph, G , that represents the currency exchange rates that exist at a given moment in time on a trading day. Each vertex in G is a currency, and each directed edge, (v, w), in G , is labeled with an exchange rate, r(v, w), which is the amount of currency w that would be exchanged for 1 unit of currency v. In order to profit from this information, you need to find, as quickly as possible, a cycle, (v₁, v₂,...,v_k, v₁), that maximizes the product, 

r(v₁, v₂) · r(v₂, v₃) ····· r(v_k, v₁), 

such that this product is strictly greater than 1. Describe and analyze an efficient dynamic programming algorithm for finding such a cycle, if it exists.