algorithm - Algo Coding 采访：从 FX 矩阵套利
问题描述
这是一个算法编码面试问题：
假设 n*n 矩阵 F 是外汇汇率矩阵 F[i][j] = f，这意味着 1 个单位 Ccyi = f 个单位 Ccyj。基于这个矩阵的最大套利是多少？注意 F[i][i]=1 和 F[i][j]*F[j][i] 不是必须的 1。例如 1 EUR = 2 USD, 1 USD = 0.6 EUR, 然后 EUR-> USD->EUR: 1 EUR => 2 USD => 1.2 EUR，有套利。
问题不完整，为了避免无限次交换，我想我们应该固定交换次数 k 并且 start Ccy 和 end Ccy 应该相同。例如k=3，Ccy1->Ccy2->Ccy3->Ccy1。我不确定这是否是一个合理的假设。
编辑：
从这里的提示：
https://anilpai.medium.com/currency-arbitrage-using-bellman-ford-algorithm-8938dcea56ea
问题只是找到最大的非重复圆。但是上面的链接使用贝尔曼福特算法只找到了套利机会（负成本圈）的存在，而不是最大的一个。