我们得到一个整数数组 A。我想找到两个具有相同加权平均值的最大长度的连续子数组（两个子数组的长度必须相等）。权重是子数组中的位置。例如
A=41111921111119 子数组
:: (11119) 和 (11119)
我试图通过 DP 找到所有子数组的加权平均值，然后按列对它们进行排序以找到具有相同长度的 2。但我无法进一步进行，而且我的方法似乎太模糊/蛮力。我将不胜感激。提前致谢。
问问题
205 次
2 回答
0
第一步应该是对数组进行排序。然后可以识别并分解出任何成对的相等值。其余的数字都会不同，如下所示：
2、3、5、9、14、19 ...等
下一步是将对与它们的中心进行比较：
2 + 5 == 2 * 3 ？
3 + 9 == 2 * 5 ？
5 + 14 == 2 * 9 ？
9 + 19 == 2 * 14 ？
下一步是比较嵌套对，这意味着如果您有 ABCD，则将 A+D 与 B+C 进行比较。因此，对于上面的示例，它将是：
2+9 == 3+5？
3+15 == 5+9 ？
5+19 == 9+14 ？
接下来，您将三元组与两个内部值进行比较：
2 + 3 + 9 == 3 * 5 ？
2 + 5 + 9 == 3 * 3 ？
3 + 5 + 14 == 3 * 9 ？
3 + 9 + 14 == 3 * 5 ？
5 + 9 + 19 == 3 * 14 ？
5 + 14 + 19 == 3 * 9 ？
然后你会比较成对的三元组：
2 + 3 + 19 == 5 + 9 + 14 ？
2 + 5 + 19 == 3 + 9 + 14 ？
2 + 9 + 19 == 3 + 5 + 14 ？
等等。有不同的方式来进行排序。一种方法是创建一个初始括号，例如，给定 ABCDEFGH，初始括号是 ABGH 与 CDEF，即外部与中心相比。然后根据比较切换值。例如，如果 ABGH > CDEF，那么您可以尝试左侧值大于右侧值的所有开关。在这种情况下，G 和 H 大于 E 和 F，因此可能的开关是：
G <-> E
G <-> F
H <-> E
H <-> F
GH <-> EF
于 2012-09-26T15:01:03.170 回答
0
首先，由于两个子数组的长度必须相等，所以可以逐步考虑从 1 到 n 的长度。
对于长度 i，您可以计算每个子数组的加权和，总复杂度为 O(n)。然后对总和进行排序以确定是否存在相等的对。
因为你排序 n 次，所以时间是 O(n^2 log n)，而空间是 O(n)。
也许我只是重复了问题中提到的解决方案？但我认为它不能再优化了......
于 2012-09-26T15:25:17.703 回答