Maximize Amount After Two Days of Conversions
You are given a string initialCurrency, and you start with 1.0 of initialCurrency.
You are also given four arrays with currency pairs as strings and rates as real numbers:
pairs1[i] = [startCurrencyi, targetCurrencyi]denotes that you can convert fromstartCurrencyitotargetCurrencyiat a rate ofrates1[i]on day 1.pairs2[i] = [startCurrencyi, targetCurrencyi]denotes that you can convert fromstartCurrencyitotargetCurrencyiat a rate ofrates2[i]on day 2.- Each
targetCurrencycan also be converted back to its correspondingstartCurrencyat a rate of1 / rate.
You can perform any number of conversions, including zero, using rates1 on day 1, followed by any number of additional conversions, including zero, using rates2 on day 2.
Return the maximum amount of initialCurrency you can have after performing any number of conversions on both days in order.
Note: Conversion rates are valid, and there will be no contradictions in the rates for either day. The rates for the days are independent of each other.
Example 1
Input
initialCurrency = "EUR", pairs1 = [["EUR","USD"],["USD","JPY"]], rates1 = [2,3], pairs2 = [["JPY","USD"],["USD","CHF"],["CHF","EUR"]], rates2 = [4,5,6]Output
720Following the conversions EUR to USD to JPY on day 1, then JPY to USD to CHF to EUR on day 2 yields 720.0 EUR, which is the maximum amount.
Example 2
Input
initialCurrency = "NGN", pairs1 = [["NGN","EUR"]], rates1 = [9], pairs2 = [["NGN","EUR"]], rates2 = [6]Output
1.5Converting NGN to EUR on day 1 and EUR back to NGN using the inverse rate on day 2 gives the maximum amount.
Constraints
- 1 <= initialCurrency.length <= 3
- initialCurrency consists only of uppercase English letters.
- 1 <= n == pairs1.length <= 10
- 1 <= m == pairs2.length <= 10
- pairs1[i] == [startCurrencyi, targetCurrencyi]
- pairs2[i] == [startCurrencyi, targetCurrencyi]
- 1 <= startCurrencyi.length, targetCurrencyi.length <= 3
- startCurrencyi and targetCurrencyi consist only of uppercase English letters.
- rates1.length == n
- rates2.length == m
- 1.0 <= rates1[i], rates2[i] <= 10.0
- The input is generated such that there are no contradictions or cycles in the conversion graphs for either day.
- The input is generated such that the output is at most 5 * 10^10.