寻找数组中索引不相交的两个最大比值对的高效算法

给定数组[1, 1, 3, 10, 11, 2, 9]，需找到两个数对[n1,n2]和[m1,m2]，使得(n2/n1)+(m2/m1)的和最大，且满足以下条件：

• n1 ≤ n2，m1 ≤ m2；
• 索引满足 index(n1) < index(n2) < index(m1) < index(m2)。

示例中符合条件的数对为[1(n1),11(n2)]和[2(m1),9(m2)]，无法选取其他如1和10的组合，因其索引会处于n1和n2之间。

当前思路 #

• 找到索引满足index(min) < index(max)的最小和最大值；
• 在它们之间找到索引满足index(max) < index(min)的另一对最小和最大值。

但无法证明该思路的正确性，也不确定是否存在其他更优方案。

已实现的暴力解法 #

时间复杂度为O(n^4)，代码如下：

def max_ratio(x):
    # x - 整数列表
    ratio = 0
    values = []
    for i in range(len(x)-3):
        for j in range(i+1, len(x)-2):
            for k in range(j+1, len(x)-1):
                for l in range(k+1, len(x)):
                    if (x[l]/x[k]) + (x[j]/x[i]) > ratio:
                        ratio = (x[l]/x[k]) + (x[j]/x[i])
                        values = [i, j, k,l]
    return [x[values[0]], x[values[1]], x[values[2]], x[values[3]]]

寻求更高效的算法。

内容的提问来源于stack exchange，提问作者Andrey